复赛
混合背包
这道题用到了01背包、多重背包和完全背包，
是一道背包问题的模板题。
核心代码就是三个背包的写法
01背包：
for (int j = v; j >= w; j--) {//每个物品只有拿或不拿两种状态，且只受到上一层（上一个物品）的前面价值的影响，而不受到这一层前面和后面的影响，所以从后向前遍历
dp[j] = max(dp[j], dp[j - w] + c);
}
完全背包：
for (int j = w; j <= v; j++) {//每个物品无论之前拿于不拿均可以选择拿或不拿，所以受到前面价值的影响，因此从前向后遍历
dp[j] = max(dp[j], dp[j - w] + c);
}
多重背包：
for (int j = v; j >= w; j--) {//每个物品可以选择拿若干个，但是只受到上一层（上一个物品）的前面价值的影响，而不受到这一层前面和后面的影响，所以从后向前遍历。注意：仍是从后向前遍历，所以`j--`！
for (int k = 0; k <= p; k++) {//可以选择不拿，所以从0个开始遍历
if (j - w * k < 0) {//如果重量超过当前背包的重量（装不下了），已经没有其他可能性，所以停止遍历
break;
}
p[j] = max(dp[j], dp[j - w * k] + k * c);//注意：因为拿了若干个，所以价值要`k*c`（今天上午就这么错了找了好久）
}
}
总结/注意：
1. 遍历方向是++还是--
2. 多重背包要考虑拿的个数
区间DP
石子合并
因为合并的石子都是连续的，
又因为合并后的石子是合并前的石子的重量和，
所以所消耗的体力就是合并的右端的石子的前缀和减去左边的之前一个石子的前缀和。
for (int len = 2; len <= n; len++) {//遍历合并后的每个长度下所需最小的体力（因为是合并后，所以至少有2个石子，所以从2开始遍历）
for (int i = 1; i + len - 1 <= n; i++) {//确定左端点，右端点不能超过总石子长度
int j = i + len - 1;//因为已经确定左端点和长度，所以右端点是固定的
dp[i][j] = 1e9;
for (int k = i; k < j; k++) {//遍历两堆石子分开的地方
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);//左、右两边边一堆石子之前消耗的体力和这一次合并消耗的体力
}
}
}
石子项链
这道题与石子合并类似，但是因为这道题的石子是一个环形，所以需要破环成链
方法就是将同样的数组保存两遍即可：
for (int i = 1; i <= n; i++) {
cin >> cnt[i];
cnt[i + n] = cnt[i];
}
另外由于变成环之后
- 起始点可以是环中任何一个地方
- 由于存储的数组长度变成
n*2，所以dp数组的范围也要扩大为dp[n*2][n*2]
int dp[605][605] = {0};//数组范围改变
for (int len = 2; len <= n; len++) {
for (int left = 1; left <= n * 2 - len + 1; left++) {//左端点改变
int right = left + len - 1;
for (int cut = left + 1; cut <= right; cut++) {
dp[left][right] = max(dp[left][right], dp[left][cut - 1] + dp[cut][right] + sum[right] - sum[left - 1]);
}
}
}
- 由于从任何一个点开始都可以（也就是合并完成之后左端点可以是任何一个，所以要遍历结果的所有可能性，取最大值输出
int output = -1e9;
for (int i = 1; i <= n; i++) {
output = max(output, dp[i][i + n - 1]);
}