lightoj1031

CODE

#include <iostream>

using namespace std;
int a[105];
int sum[105];
int dp[105][105];
int ncase;
int getsum(int a ,int b)
{
        return sum[b]-sum[a-1];
}
int main()
{
        int t;
        cin >> t;
        while(t--)
        {

                int n;
                cin >> n;

                for(int i=1;i<=n;i++)
                {
                        cin>> a[i];
                        sum[i]=sum[i-1]+a[i];
                }
                for(int l=1;l<=n;l++)
                        for(int i=1;i<=n;i++)
                {
                        int j=i+l-1;
                        dp[i][j]=getsum(i,j);
                        for(int k=1;k<l;k++)
                        {
                                dp[i][j]=max(dp[i][j],getsum(i,i+k-1)-dp[i+k][j]);
                                dp[i][j]=max(dp[i][j],getsum(j-k+1,j)-dp[i][j-k]);
                        }
                }
                cout << "Case "<<++ncase<<": "<<dp[1][n]<<endl;

        }
        return 0;
}