题目:
两个玩家A和B在玩一个取石子游戏,且每个石子都有它们各自的价值。在游戏中有这样一个规则:每次取一个石子或者连续几个都必从两端取,要么是最左端,要么是最右端,直到取完为止。两个玩家都非常聪明,他们每次都会去最优的结果。给他们N个石子,你能计算出玩家A,B各自的最后结果吗?假设总是玩家A先开局。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int d[105][105], s[105], a[105];
bool vis[105][105];
int DP(int L, int R){
if(vis[L][R]){
return d[L][R];
}
vis[L][R]=1;
int m=0;//对手的最优值,当自己取完时,m=0
for(int k=L+1; k<=R; k++){
m=min(m, DP(k, R));
}
for(int k=R-1; k>=L; k--){
m=min(m ,DP(L, k));
}
d[L][R]=s[R]-s[L-1]-m;
return d[L][R];
}
int main()
{
int n;
while(scanf("%d", &n)&&n){
s[0]=0;
memset(vis, false, sizeof(vis));
for(int i=1; i<=n ;i++){
scanf("%d", &a[i]);
s[i]=s[i-1]+a[i];
}
printf("%d\n", 2*DP(1, n)-s[n]);
}
return 0;
}
当然还可以优化:
由dp的转移方程可以知道:可以由小区间递推大区间。那么直接枚举区间长度和区间起点进行状态转移。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int d[105][105], f[105][105], g[105][105], s[105], a[105];
int main()
{
int n;
while(scanf("%d", &n)&&n){
s[0]=0;
for(int i=1; i<=n ;i++){
scanf("%d", &a[i]);
f[i][i]=g[i][i]=d[i][i]=a[i];
s[i]=s[i-1]+a[i];
}
for(int Len=1; Len<n; Len++){//枚举区间长度
for(int i=1; i+Len<=n; i++){//枚举起点
int j=i+Len;
int m=0;
m=min(m, f[i+1][j]);
m=min(m, g[i][j-1]);
d[i][j]=s[j]-s[i-1]-m;
f[i][j]=min(d[i][j], f[i+1][j]);
g[i][j]=min(d[i][j], g[i][j-1]);
}
}
printf("%d\n", 2*d[1][n]-s[n]);
}
return 0;
}