2013年9月8日 星期日

2013/9/8 UVA 10066 - The Twin Towers

/* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1007 */
#include <iostream>
#include <cstdio>

using namespace std;
int num1[101], num2[101]; int dp[101][101];
int main()
{
    int N1, N2; int cnt = 0;

    while( scanf("%d %d", &N1, &N2) != EOF )
    {
        cnt++;
        if(  N1 == 0  &&  N2 == 0  ) break;


        for(int i = 1; i <= N1; i++)
            scanf("%d", &num1[i]);

        for(int i = 1; i <= N2; i++)
            scanf("%d", &num2[i]);

        for(int i = 0; i <= N1; i++)
            dp[i][0] = 0;

        for(int i = 0; i <= N2; i++)
            dp[0][i] = 0;


        for(int i = 1; i <= N1; i++)
            for(int j = 1; j <= N2; j++)
            {
                if( num1[i] == num2[j] )
                    dp[i][j] = dp[i-1][j-1]+1;

                else
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            }

        printf("Twin Towers #%d\n", cnt);
        printf("Number of Tiles : %d\n\n", dp[N1][N2]);
    }
}

沒有留言:

張貼留言