BJTU 1688 Quartzの宝物

転送ゲート:http://acm.bjtu.edu.cn/problem/detail?pid=1688
问题解决の考え方:文字列の辞书顺の问题と似ていますが、本题の要求はもっと复雑で、最初は贪欲で解决できると思っていましたが、明らかにそんなに简単ではありません.まず両侧の数字が同じ场合を考えなければなりません.しかし、同时に内部の大小関系を考えなければなりません.相手に大きな金をもらうことはできません.当時、dpについてはまだよく知られていなかったが、本題には明らかに動的計画の思想が必要だった.
解題方法:DP+接頭辞と
コードは次のとおりです.

#include <iostream>
#include <cstdio>
using namespace std;

int sum[505];   //     
int a[505];     //save the gold
int dp[505][505];
int main()
{
    freopen("test.txt","r",stdin);
    int t,i,j;
    int l,r;
    int total;
    int n;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d",&n);
        total = 0;
        for(j=1;j<=n;j++)
        {
            scanf("%d",&a[j]);
            total += a[j];
            sum[j] = total;     //     
            dp[j][j] = a[j];
        }
        for(l=n;l>0;l--)
        {
            for(r=l+1;r<=n;r++)
            {
                int temp1,temp2;    				//              
                temp1 = a[l] + sum[r] - sum[l] - dp[l+1][r];
                temp2 = a[r] + sum[r-1] - sum[l-1] - dp[l][r-1];//dp【l】【r】    l   r             ，         
                dp[l][r] = max(temp1,temp2);
            }
        }
        printf("Case #%d: ",i);
        printf("%d %d
",dp[1][n],total-dp[1][n]);
    }
    //cout << "Hello world!" << endl;
    return 0;
}