IOI 1998] Polygon - 洛谷
这是一道区间dp问题，读完题目，很容易想到要断环成链，设$f[i][j]$为i 到 j的值最高分，不难发现如下状态方程：
$f[i][j] = max(f[i][k] + f[k][j])$
$f[i][j] = max(f[i][k] × f[k][j])$
仔细考虑，加法这样做是没有问题的，但是减法的话，由于负数，会出现一下错误
我们可以再用一共$g[i][j]$来维护最小值
加法还是一样的：
$g[i][j] = min(g[i][k] + g[k + 1][j])$
然而对于乘法，很明显有四个组合：
1.lmax*rmax
2.lmax*rmin
3.lmin*rmin
4.lmin*rmin
max = max(1,2,3,4),min = min(1,2,3,4)
代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110;
const int INF = 0x3f3f3f3f;int a[N];
char c[N];
int n;
int f[N][N], g[N][N];int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> c[i] >> a[i];c[n + i] = c[i];a[n + i] = a[i];}memset(f, -0x3f, sizeof f);memset(g, 0x3f, sizeof g);for (int i = 1; i <= (n << 1); i++) {f[i][i] = g[i][i] = a[i];}for (int len = 2; len <= n; len++) {for (int i = 1; i + len - 1 <= (n << 1); i++) {int j = i + len - 1;for (int k = i; k < j; k++) {if (c[k + 1] == 't') {f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j]);} else {int vals[4] = {f[i][k] * f[k + 1][j],f[i][k] * g[k + 1][j],g[i][k] * f[k + 1][j],g[i][k] * g[k + 1][j]};for (int t = 0; t < 4; t++) {f[i][j] = max(f[i][j], vals[t]);g[i][j] = min(g[i][j], vals[t]);}}}}}int ans = -INF;int first_edges[N], cnt = 0;for (int i = 1; i <= n; i++) {int result = f[i][i + n - 1];if (result > ans) {ans = result;cnt = 0;first_edges[cnt++] = i;} else if (result == ans) {first_edges[cnt++] = i;}}cout << ans << endl;for (int i = 0; i < cnt; i++) {if (i > 0) cout << " ";cout << first_edges[i];}cout << endl;return 0;
}