題解請參考：
http://hi.baidu.com/knowledgetime/blog/item/49355560beadbf6e0c33fabc.html以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/4 7:54:43
* File Name: uva10891.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-11);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(107);
int n,r[kMaxn],sum[kMaxn],d[kMaxn][kMaxn];
int Sum(int i,int j)
{
return sum[j]-sum[i-1];
}
int dp(int i,int j)
{
if(d[i][j]!=-1)
return d[i][j];
d[i][j]=Sum(i,j);
for(int k=i;k<j;k++)
d[i][j]=max(d[i][j],Sum(i,j)-dp(k+1,j));
for(int k=i+1;k<=j;k++)
d[i][j]=max(d[i][j],Sum(i,j)-dp(i,k-1));
return d[i][j];
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1 && n)
{
sum[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&r[i]);
sum[i]=sum[i-1]+r[i];
}
memset(d,-1,sizeof(d));
for(int i=1;i<=n;i++)
d[i][i]=r[i];
printf("%d\n",dp(1,n)-Sum(1,n)+dp(1,n));
}
return 0;
}
posted on 2011-08-04 08:19
lee1r 閱讀(608)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃