题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
时间复杂度
参考文献
C++ 代码
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
include [HTML_REMOVED]
int main() {
int N;
cin >> N;
// 读取序列
vector<int> nums;
for (int i = 0; i < N; ++i) {
int num;
while (cin >> num)
nums.push_back(num);
}
// 初始化一维动态规划数组
vector<int> dp(N, 0);
// 填表计算dp数组
for (int len = 1; len <= N; ++len) {
for (int i = 0; i + len - 1 < N; ++i) {
int j = i + len - 1;
if ((N - len) % 2 == 0) {
// 玩家一的回合
dp[i] = max(nums[i] + dp[i+1], nums[j] + dp[i]);
} else {
// 玩家二的回合
dp[i] = min(-nums[i] + dp[i+1], -nums[j] + dp[i]);
}
}
}
// 计算最终得分
int player1_score = (dp[0] + accumulate(nums.begin(), nums.end(), 0)) / 2;
int player2_score = accumulate(nums.begin(), nums.end(), 0) - player1_score;
// 输出结果
cout << player1_score << " " << player2_score << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla