【区间DP】 UVA10891 Game of Sum

这题贪心的话似乎不太可行我没想出怎么贪，所以用区间dp来解决

分析

\(f[l][r]\) 表示先手在区间 \([l, r]\) 的最优决策所能给他带来的贡献，因为区间 \([l, r]\) 的总和 \(s[l, r]\) 是一定的，那么这个最优决策在意味着最大化自己的收益同时也表示最小化对手的收益。

对于 \([l,r]\) 的先手，他有三种策略：

• 从左开始取走一定的数，最小化对手剩下的收益
• 从右开始取走一定的数，最小化对手剩下的收益
• 取走所有数，对手收益为 \(0\)

据此，可以写出状态转移方程：
\(f[l][r] = s[l][r] - min\{0, \min_{k=l+1}^r f[k][r], \min_{k=l}^{r-1} f[l][k]\}\)

直接递推复杂度为 \(O(O^3)\) ，可以考虑优化：
记 \(g[l][r] = \min_{k=l}^r f[k][r]\) ，\(h[l][r] = \min_{k=l}^{r} f[l][k]\)

有 \(g[l][r] = \min(f[l][r], \min_{k=l+1}^r f[k][r])\) ，\(h[l][r] = \min(f[l][r], \min_{k=l}^{r-1} f[l][k])\)

这样我们就可以在更新完 \(f[l][r]\) 后一起更新 \(g[l][r], h[l][r]\) ，使得复杂度降为 \(O(N^2)\)

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl ‘\n‘
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)x=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
    x*=s;
}

const int N=105;
int n, w[N], s[N];
int f[N][N], g[N][N], h[N][N];

int main(){
	while(cin>>n, n){
		rep(i,1,n) read(w[i]), s[i]=s[i-1]+w[i];
		
		rep(i,1,n) f[i][i]=g[i][i]=h[i][i]=w[i];
		rep(len,2,n) rep(l,1,n){
			int r=l+len-1;
			f[l][r]=s[r]-s[l-1]-min(0, min(g[l+1][r], h[l][r-1]));
			
			g[l][r]=min(f[l][r], g[l+1][r]), h[l][r]=min(f[l][r], h[l][r-1]);
		}
		cout<<f[1][n]-(s[n]-f[1][n])<<endl;
	}
    return 0;
}

【区间DP】 UVA10891 Game of Sum

原文：https://www.cnblogs.com/Tenshi/p/14883211.html