思路
这道题和(直线)差不多,
但在之前要先处理
比如:2 1 3 4,要变成环形, 就有下面几种结果:
2 1 3 4
1 3 4 2
3 4 2 1
4 2 1 3
然后分别DP即可
但是!!
这样太慢了, 我们可以这样做:
把 2 1 3 4 变成 2 1 3 4 2 1 3
其实就是把前面的数(除最后一个)扔到最后, 然后DP
为什么可以? 在 2 1 3 4 2 1 3 连续截取4个和前面的4种情况一样
这会快很多!!! 主要是能避免重复:
比如第一种方法中, 2 1 3会算两次
学废了吗
代码(记忆化)
#include <bits/stdc++.h>
using namespace std;
int n, a[205], sum[205];
int mem[205][205];
int dfs(int l, int r) {
if (mem[l][r] != -1)
return mem[l][r];
if (l == r)
return mem[l][r] = 0;
int ans = 1e9;
for (int k = l; k < r; k++) {
int tmp = dfs(l, k) + dfs(k + 1, r) + sum[r] - sum[l - 1];
ans = min(ans, tmp);
}
return mem[l][r] = ans;
}
int dfs2(int l, int r) {
if (mem[l][r] != -1)
return mem[l][r];
if (l == r)
return mem[l][r] = 0;
int ans = -1e9 + 5;
for (int k = l; k < r; k++) {
int tmp = dfs2(l, k) + dfs2(k + 1, r) + sum[r] - sum[l - 1];
ans = max(ans, tmp);
}
return mem[l][r] = ans;
}
int main() {
memset(mem, -1, sizeof(mem));
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int sum1 = n;
for(int i = 1; i < sum1; i++){
a[++n] = a[i];
}
for(int i = 1; i <= n; i++){
sum[i] = sum[i - 1] + a[i];
}
int r = dfs(1, n), an = 1e9;
for(int i = 1; i <= (n + 1) / 2; i++){
an = min(an, mem[i][i + (n + 1) / 2 - 1]);
}
cout << an << endl;
memset(mem, -1, sizeof(mem));
r = dfs2(1, n), an = -1e9 + 5;
for(int i = 1; i <= (n + 1) / 2; i++){
an = max(an, mem[i][i + (n + 1) / 2 - 1]);
}
cout << an;
return 0;
}