A Game(动态规划)

Dynamic Programming

Posted by Scalpel on April 27, 2016

题意:

两个人轮流从数列的两头取数,每个人每次取的数加到他的得分中,求在采取最优策略的情况下各自的得分。

思路:

设\(sum_i\)为数列num的前缀和,即\(num_1\)到\(num_i\)的和,\(ans_{i,j}\)为先手玩家在数列\(num_i\)至\(num_j\)中可以取得的最大值,因为各自采取最优策略,所以其最大值一定是取走最左边的\(num_i\)或最右边的\(num_j\)后,剩下的数列中,使后手玩家可以取的\(ans_{i+1,j}\)或\(ans_{i,j-1}\)最小,要逆推,i从n递减。

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);

const int MAXN = 101;

int main()
{
#ifndef ONLINE_JUDGE
    FILEREAD
#endif
    FIO
    int n;
    while (cin >> n)
    {
        int num[MAXN], sum[MAXN] = {0};
        int ans[MAXN][MAXN] = {0};
        for (int i = 1; i <= n; ++i)
        {
            cin >> num[i];
            sum[i] = sum[i - 1] + num[i];
            ans[i][i] = num[i];
        }
        for (int i = n; i >= 1; --i)
            for (int j = i + 1; j <= n; ++j)
                ans[i][j] = sum[j] - sum[i - 1] - min(ans[i + 1][j], ans[i][j - 1]);
        cout << ans[1][n] << " " << sum[n] - ans[1][n] << endl;
    }
    return 0;
}