Solve

USACO 3.3.5 Game1

题目解答

首次遇到博弈问题，分析问题给定一个序列{num1,num2,num3……numN}两个人分别从左右以最佳策略取值，找到第一个人的可能最大值。那么我们把问题划分得小一点得知，当前的最佳策略相当于分别选择左右两边的数字加上剩下的决策序列中的最大的。因此具备最优子结构，可以拆分为小问题解决。又因为只有两个人所以知道了一个人的状态就一定知道另一个人的。用DP[i][j]表示区间 [i,j]第一个人的最佳策略。边界条件 DP[i][i]=num[i];状态转移方程:DP[i][j]=MAX{num[i]+sum[i+1][j]-DP[i+1][j],num[j]+sum[i][j-1]-DP[i][j-1]}; 根据分析不难理解本方程。不过需要从小的区间往大的区间计算。

关于原理：因为当第一个人选择最左边时从(左+1)向后它就作为后手了，而第二个人作为先手，因此从(左+1)向后第二个人是先手，他此时的决策相当于第一个人，根据方程的意义，第一个人在余下序列的最值就是从(左+1)向后的总合，减去第二个人作为先手的最优决策。(^o^)

运行结果

Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.000 secs, 2968 KB]
Test 2: TEST OK [0.011 secs, 2968 KB]
Test 3: TEST OK [0.000 secs, 2968 KB]
Test 4: TEST OK [0.032 secs, 2968 KB]
Test 5: TEST OK [0.000 secs, 2968 KB]
Test 6: TEST OK [0.000 secs, 2968 KB]
Test 7: TEST OK [0.011 secs, 2968 KB]
Test 8: TEST OK [0.011 secs, 2968 KB]
Test 9: TEST OK [0.022 secs, 2968 KB]
Test 10: TEST OK [0.000 secs, 2968 KB]
Test 11: TEST OK [0.000 secs, 2968 KB]
Test 12: TEST OK [0.011 secs, 2968 KB]
Test 13: TEST OK [0.000 secs, 2968 KB]
Test 14: TEST OK [0.022 secs, 2968 KB]
Test 15: TEST OK [0.011 secs, 2968 KB]
Test 16: TEST OK [0.000 secs, 2968 KB]

All tests OK.
YOUR PROGRAM (‘game1’) WORKED FIRST TIME! That’s fantastic
– and a rare thing. Please accept these special automated
congratulations.

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <fstream>
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;
ofstream fout ("game1.out",ios::out);
ifstream fin ("game1.in",ios::in);
long sum[101],n,dp[101][101];

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>dp[i][i];
        sum[i]=sum[i-1]+dp[i][i];
    }
    for(int k=0;k<n;k++)
        for(int i=1;i<=n-k;i++)
            for(int j=i;j<=i+k;j++)
                dp[i][j]=MAX(sum[j]-sum[i-1]-dp[i+1][j],sum[j]-sum[i-1]-dp[i][j-1]);
    fout<<dp[1][n]<< ' '<<sum[n]-dp[1][n]<<endl;
    return 0;
}

后记

本文是百度空间的移植，附：全部USACO题目解答。