https://vjudge.net/contest/303039#problem/E
大概题意：
给你字符串a、b、c，那么c是否可能由a、b组成（a，b可以打散，顺序组成c）
dp思想：
原沙雕思想：dp数组为string类型的，根据a和b一步步递推出所有能组合的字符串，当然内存超限了，像bfs想法
dp[[i][j]表示a数组取i个，b数组取j个能组成的字符串
#include <iostream> #include <algorithm> #include <queue> #include <string> #define rep1(i,s,e,c) for(int i=s;i<e;i=i+c) #define rep2(i,s,e,c) for(int i=s;i<=e;i=i+c) #define rep3(i,e,s,c) for(int i=e;i>=s;i=i-c) using namespace std; typedef long long ll; const int MAX=2e5+1; const int MOD=1e9+7; string str[2005][2005]; int main() { string a,b,c; while(cin>>a>>b>>c){ str[0][0]=""; for(int i=0;i<=a.length();i++){ for(int j=0;j<=b.length();j++){ if(i+1<=a.length()&&str[i+1][j]!=c.substr(0,i+j+1)){ str[i+1][j]=str[i][j]+a[i]; } if(j+1<=b.length()&&str[i][j+1]!=c.substr(0,i+j+1)){ str[i][j+1]=str[i][j]+b[j]; } } } if(str[a.length()][b.length()]==c){ cout<<"Yes\n"; } else cout<<"No\n"; } return 0; }新写法：
dp[i][j]表示a数组前i个字符和b数组前j个字符和c前i+j个字符是否匹配，0则不匹配，1则匹配
dp[i][j]=dp[i-1][j] | dp[i][j-1]（我是反过来递推的）
注意这种dp一定要写
if(a.length()+b.length()!=c.length()){ cout<<"No\n"; continue; }
否则例如 a:aaa b:bbb c:aaabbbx 的情况就会出错
#include <iostream> #include <algorithm> #include <queue> #include <string> #include <cstring> #define rep1(i,s,e,c) for(int i=s;i<e;i=i+c) #define rep2(i,s,e,c) for(int i=s;i<=e;i=i+c) #define rep3(i,e,s,c) for(int i=e;i>=s;i=i-c) using namespace std; typedef long long ll; const int MAX=2e5+1; const int MOD=1e9+7; int dp[2005][2005]; int main() { string a,b,c; while(cin>>a>>b>>c){ if(a.length()+b.length()!=c.length()){ cout<<"No\n"; continue; } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=0;i<=a.length();i++){ for(int j=0;j<=b.length();j++){ if(a[i]==c[i+j]){ dp[i+1][j]|=dp[i][j]; } if(b[j]==c[i+j]){ dp[i][j+1]|=dp[i][j]; } } } if(dp[a.length()][b.length()]==1){ cout<<"Yes\n"; } else cout<<"No\n"; } return 0; }
