在基础上新加了可以合并开头和结尾俩堆石子。
以样例为例,最小得分的方案:
1、合并4 4 -> 8,得分8
2、合并8 5 -> 13,得分13
3、合并13 9 -> 22,得分22
总得分8 + 13 + 22 = 43
朴素想法:每合并1次用边将俩石子相连,因为长为n,所以合并n-1次,而n的环相邻可连n条边,总有俩石子之间没有边(样例就是5和9之间),枚举这个的位置,将其拆成链,用之前的做法得到答案。这样时间复杂度是O(n4),会超时。
对于环的常用方法,是将环拆成链再复制一遍接在后面,变成长度为2n-1的链。
例如,1 2 3 4可以变成1 2 3 4 1 2 3,对这个链任取长度为n的区间,和在环上取区间等价。
#include <iostream>
#include <cstring>
using namespace std;
int n, a[305], sum[605], f[605][605], g[605][605];
int main() {
scanf("%d", &n);
memset(f, 0x3f, sizeof(f));
//memset(g, -0x3f, sizeof(g));
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
}
for (int i = 1; i < 2 * n; i ++ ) {
f[i][i] = 0;
g[i][i] = 0;
sum[i] += sum[i - 1] + a[(i - 1) % n + 1];
}
for (int l = 2; l <= n; l ++ ) {
for (int i = 1; i + l - 1 < 2 * n; i ++ ) {
int j = i + l - 1;
for (int k = i; k < j; k ++ ) {
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + sum[j] - sum[i - 1]);
}
}
}
int min_ans = 0x3f3f3f3f;
int max_ans = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++ ) {
min_ans = min(min_ans, f[i][i + n - 1]);
max_ans = max(max_ans, g[i][i + n - 1]);
}
printf("%d\n%d\n", min_ans, max_ans);
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁