最长公共子序列
#include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; int a[110]; int b[110]; int dp[110][110]; int dfs(int i,int j) { if(i<0||j<0) return 0; if(dp[i][j]!=-1) return dp[i][j]; if(a[i]==b[j]) dp[i][j]=dfs(i-1,j-1)+1; else dp[i][j]=max(dfs(i-1,j),dfs(i,j-1)); return dp[i][j]; } int main() { int cs=0,n,m,i,j; while(cin>>n>>m) { if(n==0||m==0) break; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<m;i++) cin>>b[i]; memset(dp,-1,sizeof(dp)); dfs(n-1,m-1); printf("Twin Towers #%d\nNumber of Tiles : %d\n\n",++cs,dp[n-1][m-1]); } return 0; }
#include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; int a[110]; int b[110]; int dp[110][110]; int main() { int cs=0,n,m,i,j; while(cin>>n>>m) { if(n==0||m==0) break; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<m;i++) cin>>b[i]; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); printf("Twin Towers #%d\nNumber of Tiles : %d\n\n",++cs,dp[n][m]); } return 0; }