WAP2017在线面试题——两端取数

题目

题目内容

有A，B两个玩家，分别对一列n个数的队列取数，每个玩家每次可挑选队列两端的数，A先取，直到取完，最终取到的数值之和大的获胜，若相等，则A获胜，假设两个玩家都经过了充分的思考，现给定长度为n的数队列，问A是否能获胜，如果A能输出yes，否则输出no。

输入

输入为一行，第一个数字为n，后面有n个数字，为队列内的数字

输出

输出为一行，yes或者no

输入输出样例

输入：3 1 5 2
输出：no

输入：4 5 7 10 2
输出：yes

解题思路

是一道DP题目，将问题转化成对于区间i到j，先手比后手的分数差的最大值为dp[i,j]，可以得到状态转移方程：
![][1]
[1]:http://latex.codecogs.com/gif.latex?dp%5Bi.j%5D%20%3D%20%5Cleft%5C%7B%5Cbegin%7Baligned%7D%26a%5Bi%5D%2Ci%3Dj%5C%5C%26max%28a%5Bi%5D-dp%5Bi+1%2Cj%5D%2Ca%5Bj%5D-%20dp%5Bi%2Cj-1%5D%29%2Celse%20%5Cend%7Baligned%7D

代码

#include <bits/stdc++.h>

int main(void) {
    int n;
    while (std::cin >> n) {
        std::vector<int> a(n + 5);
        std::vector<std::vector<int>> dp(n + 5, std::vector<int>(n + 5, 0));
        for (int i = 1; i <= n; i++) {
            std::cin >> a[i];
            dp[i][i] = a[i];
        }
        for (int k = 1; k < n; k++) {
            for (int i = 1; i <= n - k; i++) {
                int j = i + k;
                dp[i][j] = std::max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]);
            }
        }

        if (dp[1][n] >= 0) std::cout << "yes" << std::endl;
        else std::cout << "no" << std::endl;

    }
    return 0;
}