鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

最长公共子序列的时间排名表

来源:互联网 作者:佚名 时间:2015-09-25 05:36
题目意思: 给1-n个事件的正确发生 时间 排名表 ,再给一个1-n个事件的 时间 排名表 ,求最长的事件个数,是相对排名的顺序与正确的一样。 解题思路: 按照排名的顺序整理事件,然后求最长 公共 子 序列 的长度。 dp[i][j]=dp[i-1][j-1]+1(save1[i]==save[j
    题目意思:
    给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
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #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;
    }
    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;
    }

【责编:peter】
网友评论
<