codevs3196 黄金宝藏

题目描述 Description

小毛终于到达宝藏点，他意外地发现有一个外星人（名叫Pluto）。宝藏是一些太空黄金，有n堆排成一行，每堆中有xi颗黄金。小毛和Pluto决定轮流从中取出黄金，规则是每次只能从最左边或最右边取出一堆黄金，直到所有黄金被取出。小毛先取，两人都以最优策略进行选取，求两人的最后所得。

输入描述 Input Description

第一行是正数n(≤500)；第二行为n个正整数xi(≤300)，表示每堆黄金的个数。

输出描述 Output Description

仅两个整数，分别表示小毛和Pluto的得分，以空格隔开。

样例输入 Sample Input

4 7 2 9 5 2

样例输出 Sample Output

18 11

正解：DP

解题报告：
　　看到这是博弈的时候有一点慌。。。好吧其实只用了思想。

　　显然DP可行，f[i][j]表示从i到j的区间的最优策略，最后f[1][n]即先手得分，总和减掉这个最优值即为后手得分。

　　转移也比较好想，只是有一个地方比较神。显然由从左端选了一堆或者从右端选了一堆转移过来，而我们取得是较小的那个值，因为我们需要后手决策尽可能贡献小。

　　细节看代码吧。

 //It is made by jump~

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 #ifdef WIN32

 #define OT "%I64d"

 #else

 #define OT "%lld"

 #endif

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 int n;

 int a[MAXN],sum[MAXN];

 int f[MAXN][MAXN];//f[i][j]表示从i到j的最优策略得分

 inline int getint()

 {

        int w=,q=;

        char c=getchar();

        while((c<'' || c>'') && c!='-') c=getchar();

        if (c=='-')  q=, c=getchar();

        while (c>='' && c<='') w=w*+c-'', c=getchar();

        return q ? -w : w;

 }

 inline void work(){

     n=getint();

     for(int i=;i<=n;i++) a[i]=getint(),f[i][i]=a[i],sum[i]=sum[i-]+a[i];

     for(int len=;len<=n-;len++)

     for(int i=;i<=n-len;i++)

         f[i][i+len]=sum[i+len]-sum[i-]-min(f[i+][i+len],f[i][i+len-]);//减去部分是后手的决策最小值

     printf("%d %d",f[][n],sum[n]-f[][n]);//总和减去先手最优决策即为后手得分

 }

 int main()

 {

   work();

   return ;

 }

秒客网

codevs3196 黄金宝藏

相关文章