首页 > 代码库 > Uva 10891

Uva 10891

2024-08-25 00:22:14   210人阅读

经典博弈区间DP

题目链接：https://uva.onlinejudge.org/external/108/p10891.pdf

题意：

给定n个数字，A和B可以从这串数字的两端任意选数字，一次只能从一端选取。

并且A B都尽力使自己选择的结果为最大的，可以理解成A B每一步走的都是最优的。

如果A先选择，则A B差值最大是多少。

 

分析：

总和是一定的，所以一个得分越高，另一个人的得分越低。当前状态总是最开始的状态的一个子状态。

d(i,j): 先手取 i ~ j 最优策略下，得分最大值。

 

d(i,j) = sum(i,j) - min(d(i+1,j),d(i+2,j),...,d(j,j),  d(i,j-1),d(i,j-2),...,d(i,i),0)

0表示全部取完；

 

答案就是 d(1,n) - ( sum(1,n) - d(1,n) )；

tip： sum(i,j) 可以在 O(1) 的时间内求出来。 S[i] 是 1~ i 的和，那么 sum(i,j) = S[j] - S[i-1];

#include <bits/stdc++.h>using namespace std;int n;const int maxn = 100 + 10;int S[maxn],A[maxn],d[maxn][maxn],vis[maxn][maxn];int dp(int i,int j) {    if(vis[i][j])        return d[i][j];    vis[i][j] = 1;    int m = 0;    for(int k=i+1;k<=j;k++)        m = min(m,dp(k,j));    for(int k=i;k<j;k++)        m = min(m,dp(i,k));    d[i][j] = S[j] - S[i-1] - m;    return d[i][j];}int main(){    while(scanf("%d",&n)==1&&n) {        S[0] = 0;        for(int i=1;i<=n;i++) {            scanf("%d",&A[i]);            S[i] = S[i-1] + A[i];        }        memset(vis,0,sizeof(vis));        printf("%d\n",2*dp(1,n)-S[n]);    }    return 0;}

 

Uva 10891


联系
我们