首先,我们需要初始化两个数组,一个用于存储输入的数列`a[]`,另一个用于动态规划过程中存储中间结果的二维数组`dp[][]`。`dp[i][j]`表示从数列的第`i`个数到第`j`个数时,当前玩家(甲方先手)能够获得的最大得分。
接下来,我们按照以下步骤进行动态规划:
1. 初始化`dp[i][i]`为`a[i]`,因为如果数列中只有一个数,当前玩家只能取这一个数。
2. 计算所有可能的数列长度(从2开始到n),对于每个长度,计算所有可能的起始位置i(从1到n-length+1)。
3. 对于每个起始位置i,计算结束位置j(i+length-1),然后根据动态规划的状态转移方程更新`dp[i][j]`。
4. 状态转移方程为:`dp[i][j] = sum(i,j) - min(dp[i+1][j], dp[i][j-1])`,其中`sum(i,j)`是从第i个数到第j个数的总和,可以通过前缀和数组预先计算以优化时间复杂度。
5. 最终,`dp[1][n]`就是甲方在最优策略下能获得的最大得分,乙方的得分则为总和减去`dp[1][n]`。
下面是具体的C++实现代码:
#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<int> a(n+1);vector<vector<int>> dp(n+1, vector<int>(n+1));vector<int> sum(n+1, 0); // 前缀和数组// 读入数列并计算前缀和for (int i = 1; i <= n; ++i) {cin >> a[i];sum[i] = sum[i-1] + a[i];}// 初始化dp数组for (int i = 1; i <= n; ++i) {dp[i][i] = a[i];}// 动态规划计算dp数组for (int length = 2; length <= n; ++length) {for (int i = 1; i <= n - length + 1; ++i) {int j = i + length - 1;int total = sum[j] - sum[i-1]; // 计算当前数列的总和dp[i][j] = total - min(dp[i+1][j], dp[i][j-1]);}}// 输出甲乙双方的得分cout << dp[1][n] << " " << (sum[n] - dp[1][n]) << endl;return 0;
}
这段代码首先读取数列的长度和数列本身,然后计算前缀和以便快速计算任意子数列的总和。接着,通过动态规划填充`dp`数组,最后输出甲乙双方的得分。