ZOJ 2059——The Twin Towers解題報告

3145 ワード

とても経典的なDPタイトルだそうです.ソースは浙江省大月戦です.
問題解決資料を参考にする:http://allen303allen.bokee.com/viewdiary.19263200.html
 
自分のコード:
/*
ZOJ 2059 —— The Twin Towers
        ,      2   ,           ,           。     2        。
       3   ,    ,         ,         。
         ?            2000,          100     3^100,  gg 。
                ,   2000       ,    2001    。
                i    ,          。
         ,                        ,      ,            2   :
1.          
2.       ,              , 
        ,      。
      :h[i]  i   ,dp[i][j]    i    ,    j         
    dp[i][j+h[i]] = max(dp[i][j+h[i], dp[i-1][j] + h[i]); //        。 
    if ( h[i] > j ) //h[i]    j ,    h[i]   dp[i-1][j]        。
        dp[i][h[i]-j] = max(dp[i][h[i]-j], dp[i-1][j] + h[i]-j);
    else           //h[i]    j  ,    h[i]        , 
        dp[i][j-h[i]] = max(dp[i][j-h[i]], dp[i-1][j] ); 
          ,    ,     , j    ,              。 
*/
#include <iostream>
#include <cstdio>


int max(const int a, const int b)
{
    if ( a > b )
        return a;
    else
        return b;
}
int min(const int a, const int b)
{
    if ( a > b )    return b;
    else    return a;
} 
int main()
{
    int dp[2][2001], a[101];
    int n, i, j;
    int sum ;
    int t;
    while ( scanf("%d", &n ) != EOF && n != -1 )
    {
        sum = 0;
        for ( i = 1; i <= n; ++i )
        {    
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sum = min(sum, 2000);
        for ( i = 0; i <= sum; ++i )
            dp[0][i] = -1;
        dp[0][0] = 0;
        dp[0][a[1]] = a[1];
        t = 0;
        for ( i = 2; i <= n; ++i )
        {
            t = 1-t;
            for ( j = 0; j <= sum; ++j )
                dp[t][j] = -1;
            for ( j = 0; j <= sum; ++j )
            {
                dp[t][j] = max(dp[t][j], dp[1-t][j]);
                if ( dp[1-t][j] == -1 )
                    continue;
                if ( j + a[i] <= sum ) //    tower  
                    dp[t][j+a[i]] = max(dp[1-t][j]+a[i], dp[t][j+a[i]]);     
                if ( j >= a[i] ) //           
                {
                    dp[t][j-a[i]] = max(dp[t][j-a[i]], dp[1-t][j]);
                }
                else //           
                {
                    dp[t][a[i]-j] = max(dp[t][a[i]-j], dp[1-t][j] + a[i]-j); 
                }
                
            }
            
        }
             
        
        
        if ( dp[t][0] > 0 )
            printf("%d
",dp[t][0]); else printf("Sorry
"); } return 0; }