题解 P3025 【[USACO11OPEN]忘记密码Forgotten Password】
ycyaw
·
·
题解
或许你们更愿意看短一点的代码。
每个密码单词长度小于等于20，那么我们在dp时直接暴力判断能不能匹配。
代码很短很好懂：
复杂度$O(L\times NW\times 20)$。
```cpp
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
using namespace std;
int len,n;
char p[1005];
string s[1005],ans[1005];
inline int read(){
int ret=0,ff=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
while(isdigit(ch)){ret=ret*10+(ch^48);ch=getchar();}
return ret*ff;
}
inline bool check(int st,int id){
for(int i=0;i<s[id].size();i++)
if(p[st+i]!='?'&&p[st+i]!=s[id][i])
return 0;
return 1;
}
signed main(){
len=read(),n=read();
scanf("%s",p+1);
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=len;i++){
for(int j=1;j<=n;j++){
if(s[j].size()>i) continue;
int st=i-s[j].size();
if(st>0&&ans[st]=="") continue;
if(check(st+1,j))
if(ans[i]==""||ans[i]>ans[st]+s[j])
ans[i]=ans[st]+s[j];
}
}
cout<<ans[len];
return 0;
}
```