題目意思： 給1-n個事件的正確發生時間排名表，再給一個1-n個事件的時間排名表，求最長的事件個數，是相對排名的順序與正確的一樣。 解題思路： 按照排名的順序整理事件，然後求最長公共子序列的長度。 dp[i][j]=dp[i-1][j-1]+1(save1[i]==save[j]) dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 代碼： #include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #define eps 1e-6 #define INF (1<<20) #define PI acos(-1.0) using namespace std; int save1[30],save2[30]; int dp[30][30]; int main() { int n,temp; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&temp); save1[temp]=i; //以排名為順序，重新整理事件，使最長公共子序列有相對一樣的排名 } while(scanf("%d",&temp)!=EOF) { save2[temp]=1; for(int i=2;i<=n;i++) { scanf("%d",&temp); save2[temp]=i; } www.2cto.com memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(save1[i]==save2[j]) dp[i][j]=dp[i-1][j-1]+1;//max(max(dp[i-1][j-1]+1,dp[i-1][j]),dp[i][j-1]); else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } printf("%d\n",dp[n][n]); } return 0; }
