uva--111History Grading +dp

uva--111History Grading +dp

題意：

其實就是求兩個序列的最長公共子序列。

思路：

這個題目的輸入是很坑爹的，如果把輸入理解清楚後，這個題目就不難了。題目的輸入表示的是該位置上的數放在哪個位置上，比如說輸入是1,3,2,4其對應的序列應該是1,3,2,4;

下面給出2份代碼，一份是經典的解法，一份是今天我寫的把問題轉成DAG圖上的最長路求解的代碼。

代碼如下：

#include
#include
#include
using namespace std;

int d[30],n,map[30][30];

int dp(int i)
{
    if(d[i]>0) return d[i];
    d[i]=1;
    for(int j=1;j<=n;j++)
        if(map[i][j])
        {
            int t=dp(j)+1;
            if(d[i]


#include
#include
#include
using namespace std;

int main()
{
    int i,j,a[30],b[30],dp[30][30],n;
    while(scanf("%d",&n)!=EOF)
    {
         int x;
         for(i=1;i<=n;i++)
         {
             scanf("%d",&x);
             a[x]=i;
         }
         while(scanf("%d",&x)!=EOF)
         {
             b[x]=1;
             for(i=2;i<=n;i++)
             {
                 scanf("%d",&x);
                 b[x]=i;
             }
           memset(dp,0,sizeof(dp));
           for(i=1;i<=n;i++)
              for(j=1;j<=n;j++)
              {
                     if(a[i]==b[j])
                          dp[i][j]=dp[i-1][j-1]+1;
                     else
                           dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
              }
              int ans=0;
              for(i=1;i<=n;i++)
                 for(j=1;j<=n;j++)
                      ans=max(ans,dp[i][j]);
              printf("%d\n",ans);
         }
    }
  return 0;
}