题目
题目内容
有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;
}
