題目
題目內(nèi)容
有A桃笙，B兩個玩家，分別對一列n個數(shù)的隊列取數(shù)假抄，每個玩家每次可挑選隊列兩端的數(shù)怎栽，A先取，直到取完宿饱，最終取到的數(shù)值之和大的獲勝熏瞄，若相等，則A獲勝谬以，假設(shè)兩個玩家都經(jīng)過了充分的思考强饮，現(xiàn)給定長度為n的數(shù)隊列，問A是否能獲勝为黎，如果A能輸出yes邮丰，否則輸出no。
輸入
輸入為一行铭乾，第一個數(shù)字為n剪廉，后面有n個數(shù)字，為隊列內(nèi)的數(shù)字
輸出
輸出為一行炕檩，yes或者no
輸入輸出樣例
輸入：3 1 5 2
輸出：no
輸入：4 5 7 10 2
輸出：yes
解題思路
是一道DP題目斗蒋，將問題轉(zhuǎn)化成對于區(qū)間i到j(luò)，先手比后手的分?jǐn)?shù)差的最大值為dp[i,j]笛质，可以得到狀態(tài)轉(zhuǎn)移方程：
![][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;
}
