BZOJ3297: [USACO2011 Open]forgot（背包）

3297: [USACO2011 Open]forgot

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 189 Solved: 126
[Submit][Status][Discuss]

Description

发生了这么多，贝茜已经忘记了她cowtube密码。然而，她记得一些有用的信息。首先，她记得她的密码（记为变

量P）长度为L（1 <= L<=1,000）字符串，并可以被分成一个或多个词（不一定是唯一的），词来自于字典中NW（

1<=NW<=1,000）个独特的词。一个词W_i，被定义为一个长度1..20的小写字母序列('a'..'z')。她还记得她密码

中某些字母的位置。

请看下面的例子。

贝西知道她的密码看起来像"a??l?ban???????"（'？'代表一个字母，她不记得），

她的字典里有下面的词：

apple

cow

farmer

banana

bananas

pies

贝西有两个可能的密码是的“applebananapies”和“applebananascow”。

给你字典，贝西记得的字母，请找到她的密码。如果有一个以上的密码是可能的，找到字典序最前的。

Input

*第1行：两个空格分隔的整数：L和NW

*第2行：一个字符串，长度为L：P

*第3..N+2W行：第I+2行包含在字典中的第i个字：W_i

Output

*第1行：密码

Sample Input

15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies

Sample Output

applebananapies

HINT

Source

Silver

思路：最开始在想AC自动机，然后在自动机上跑DP，会出现空间不足，以及没有高效办法求最小字典序的问题。

然后发现可以用O(N*M*L)的背包来写。但是写起来可能比较麻烦，一下别人的代码，还真是。巧妙的是，如果我们直接用string的话，代码写起来非常方便，比较大小也直接比较。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

string c,s[maxn],dp[maxn];int N,M,L[maxn];

bool check(int t,int p)

{

    rep(i,,L[p]-) if(c[i+t]!='?'&&c[i+t]!=s[p][i]) return false;

    return true;

}

int main()

{

    cin>>N>>M>>c;

    rep(i,,M) cin>>s[i],L[i]=s[i].length();

    rep(i,,N) {

        rep(j,,M){

            if(i<L[j]||(i-L[j]!=&&dp[i-L[j]]=="")) continue;

            if(check(i-L[j],j))

              if(dp[i]==""||dp[i-L[j]]+s[j]<dp[i]) dp[i]=dp[i-L[j]]+s[j];

        }

    }

    cout<<dp[N]<<endl;

    return ;

}

nw