Uva(10891)(Game of Sum)
2018-08-08 本文已影响0人
kimoyami
链接:https://vjudge.net/problem/UVA-10891
思路:其实我一开始没有看出来这是一个动态规划的题目,不过我们可以来思考一下,设d(i,j)为先手所能取得的最好的最大的分差,那么我们怎么表示这个d(i,j)呢,我们知道,总和是一定的,你取了多少分,马上可以算出对手取了多少分,那么d(i,j)就可以i表示为sum(i,j)-min(d(i+1,j),d(i+2,j).......d(i,j-1),d(i,j-2).....d(i,i+1),0)(注意0表示对手决策用完,即我一把把所有的都全部抓完,对手从而没有东西可以抓了,这种情况一定不要漏掉!!!),然后用dd[][]保存已经计算出的值,记忆式搜索求出答案。
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,sum[101][101],a[101],dd[101][101];
int d(int i,int j){
if(dd[i][j]!=0)return dd[i][j];//保存已经搜索出的值
if(i==j)return a[i];
int minn = 0;//一把抓完所有的
//取最小值
for(int k=i+1;k<=j;k++){
minn = min(minn,d(k,j));
}
for(int k=j-1;k>=i;k--){
minn = min(minn,d(i,k));
}
dd[i][j] = sum[i][j] - minn;//保存当前最优解
return dd[i][j];//返回最优解
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(cin>>n&&n){
memset(sum,0,sizeof(sum));
memset(dd,0,sizeof(dd));
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
for(int k=i;k<=j;k++){
sum[i][j]+=a[k];
}
}
}
cout<<2*d(1,n)-sum[1][n]<<endl;//结果等于d(i,j)-(sum(i,j)-d(i,j)),即原式
}
return 0;
}
老刘的o(n^2)解法暂时没看懂,先放这里吧
Uva(10891)(Game of Sum)