題目大意：輸入字符串a,b,c 要求推斷c是否有a,b中的個字符保持原有順序組合而成。

算法思想：

DP

用dp[i][j]表示a的前0~i-1共i個字符和b的前0~j-1共j個字符是否構成c[i+j-1].

狀態轉換方程：

if(i>=1&&c[i+j-1]==a[i-1])

dp[i][j]=dp[i][j]||dp[i-1][j]

if(j>=1&&c[i+j-1]==b[j-1])

dp[i][j]=dp[i][j]||dp[i][j-1]

代碼例如以下：

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int main(){int n;cin>>n;for(int i=1;i<=n;i++){char a[250];char b[250];char c[550];scanf("%s%s%s",a,b,c);int la=strlen(a);int lb=strlen(b);int lc=strlen(c);int dp[250][250];memset(dp,0,sizeof(dp));dp[0][0]=1;if(a[0]==c[0])dp[1][0]=1;if(b[0]==c[0])dp[0][1]=1;for(int j=0;j<=la;j++){for(int k=0;k<=lb;k++){if(k>=1&&c[k+j-1]==b[k-1])dp[j][k]=dp[j][k]||dp[j][k-1];if(j>=1&&c[k+j-1]==a[j-1])dp[j][k]=dp[j][k]||dp[j-1][k];}}if(dp[la][lb])cout<<"Data set "<<i<<": yes"<<endl;else cout<<"Data set "<<i<<": no"<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的ACM POJ 2192 Zipper的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。