dp 最长公共子序列 uva 111-History Grading


 
 
题目意思：
 
   给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.zzzyk.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;
}

补充：软件开发 , C++ ,