UVA 10891 Game of Sum(区间DP(记忆化搜索))

题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832

题目大意:

两个人在玩一个游戏:

给你一行n个数字,每次只能从左端或者右端取一个或多个数字。

每个人的分值就是他们各自取得的数字之和。

假设两人都足够聪明,问先手最多能比后手多多少分。

解题思路:

其实题目意思就是先手最多能得到多少分。

设dp[l][r]是取完[l,r]的数字时先手能获得的最大分值,sum是[l,r]的数字之和。

那么可以得到状态转移方程:

dp[l][r]=max(dp[l][r],sum-dp[i+1][r]),(l=<i<=r)

dp[l][r]=max(dp[l][r],sum-dp[l][i-1]),(l<=i<=r)

这里sum-子区间最优解的操作相当于取反,就是子区间的先手变成了后手,后手变成了先手的意思。

代码:

 #include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=1e3+;
const int INF=0x3f3f3f3f;
const double eps=1e-; int a[N],dp[N][N]; int solve(int l,int r){
if(l>r) return ;
if(dp[l][r]!=-INF)
return dp[l][r];
int sum=a[r]-a[l-];
//从左端取
for(int i=l;i<=r;i++){
dp[l][r]=max(dp[l][r],sum-solve(i+,r));
}
//从右端取
for(int i=r;i>=l;i--){
dp[l][r]=max(dp[l][r],sum-solve(l,i-));
}
return dp[l][r];
} int main(){
int n;
while(cin>>n&&n){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
dp[i][j]=-INF;
}
}
for(int i=;i<=n;i++){
cin>>a[i];
dp[i][i]=a[i];
a[i]+=a[i-];
}
solve(,n);
cout<<*dp[][n]-a[n]<<endl;
}
return ;
}
上一篇:UVa 10891 Game of Sum - 动态规划


下一篇:thinkphp模板中,checkbox回显问题