经典水题.......
断环为链长度乘二，求前缀和区间DP。
1 #include2 #include 3 #include 4 #define int long long 5 const int N = 210; 6 7 int f[N][N], sum[N]; 8 9 main() {10 int n;11 scanf("%lld", &n);12 for(int i = 1; i <= n; i++) {13 scanf("%lld", &sum[i]);14 sum[n + i] = sum[i];15 }16 memset(f, 0x3f, sizeof(f));17 for(int i = 1; i <= n << 1; i++) {18 sum[i] += sum[i - 1];19 f[i][i] = 0;20 }21 22 23 for(int len = 2; len <= n; len++) {24 for(int l = 1; l + len - 1 <= n << 1; l++) {25 int r = l + len - 1;26 for(int k = l; k < r; k++) {27 f[l][r] = std::min(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);28 }29 }30 }31 32 int ans = 0x3f3f3f3f3f3f3f3f;33 for(int i = 1; i <= n; i++) {34 ans = std::min(ans, f[i][i + n - 1]);35 }36 printf("%lld\n", ans);37 38 memset(f, 0, sizeof(f));39 for(int len = 2; len <= n; len++) {40 for(int l = 1; l + len - 1 <= n << 1; l++) {41 int r = l + len - 1;42 for(int k = l; k < r; k++) {43 f[l][r] = std::max(f[l][r], f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);44 }45 }46 }47 ans = 0;48 for(int i = 1; i <= n; i++) {49 ans = std::max(ans, f[i][i + n - 1]);50 }51 printf("%lld", ans);52 return 0;53 }
这里用了个define int long long的骚操作，不推荐，可能爆0。