ZOJ 2059——The Twin Towers解題報告
3145 ワード
とても経典的なDPタイトルだそうです.ソースは浙江省大月戦です.
問題解決資料を参考にする:http://allen303allen.bokee.com/viewdiary.19263200.html
自分のコード:
問題解決資料を参考にする: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;
}