首页 > 代码库 > UVa 10891 (博弈+DP) Game of Sum

UVa 10891 (博弈+DP) Game of Sum

2024-07-17 08:01:30   219人阅读

最开始的时候思路就想错了，就不说错误的思路了。

因为这n个数的总和是一定的，所以在取数的时候不是让自己尽可能拿的最多，而是让对方尽量取得最少。

记忆化搜索：

d(i, j)表示原序列中第i个元素到第j个元素构成的子序列，先手取数能够得到的最大值。

sum(i, j) 表示从第i个元素到第j个元素的和

因为要让对手获得最小的分数，所以状态转移方程为：

d(i, j) = sum(i, j) - min{d(枚举所有可能剩给对手的序列), 0(0代表全部取完)}

s数组保存a中前i个元素的和,这样sum(i, j) = s[j] - s[i-1]

 

 1 #define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 100 + 10; 9 int a[maxn], s[maxn], d[maxn][maxn], vis[maxn][maxn];10 11 int dp(int i, int j)12 {13     if(vis[i][j])14         return d[i][j];15     vis[i][j] = 1;16     int m = 0;17     for(int k = i + 1; k <= j; ++k)18         m = min(m, dp(k, j));19     for(int k = j - 1; k >= i; --k)20         m = min(m, dp(i, k));21     d[i][j] = s[j] - s[i-1] - m;22     return d[i][j];23 }24 25 int main(void)26 {27     #ifdef LOCAL28         freopen("10891in.txt", "r", stdin);29     #endif30 31     int n;32     while(scanf("%d", &n) == 1 && n)33     {34         s[0] = 0;35         for(int i = 1; i <= n; ++i)36         {37             scanf("%d", &a[i]);38             s[i] = s[i-1] + a[i];39         }40         memset(vis, 0, sizeof(vis));41         printf("%d\n", 2*dp(1, n) - s[n]);42     }43     return 0;44 }
代码君

 


联系
我们