1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include <bits/stdc++.h> using namespace std;
const int MAXN = 200; int f[MAXN][MAXN], g[MAXN][MAXN]; int num[MAXN]; char op[MAXN];
int max(int x, int y, int z, int t, int q) { return max(q, max(max(x, y), max(z, t))); }
int min(int x, int y, int z, int t, int q) { return min(q, min(min(x, y), min(z, t))); }
int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> op[i] >> num[i]; num[i + n] = num[i]; op[i + n] = op[i]; } memset(f, 0xcf, sizeof(f)); memset(g, 0x3f, sizeof(g)); for (int i = 1; i <= n * 2; ++i) { f[i][i] = num[i]; g[i][i] = num[i]; } for (int len = 2; len <= n * 2; ++len) { for (int i = 1, j = len; j <= n * 2; ++i, ++j) { for (int k = i + 1; k <= j; ++k) { if (op[k] == 't') { f[i][j] = max(f[i][j], f[i][k - 1] + f[k][j]); g[i][j] = min(g[i][j], g[i][k - 1] + g[k][j]); } else { f[i][j] = max(f[i][j], f[i][k - 1] * f[k][j], f[i][k - 1] * g[k][j], g[i][k - 1] * f[k][j], g[i][k - 1] * g[k][j]); g[i][j] = min(g[i][j], f[i][k - 1] * f[k][j], f[i][k - 1] * g[k][j], g[i][k - 1] * f[k][j], g[i][k - 1] * g[k][j]); } } } } int ans = -(1 << 30); for (int i = 1; i <= n; ++i) { ans = max(ans, f[i][i + n - 1]); } cout << ans << endl; for (int i = 1; i <= n; ++i) { if (f[i][i + n - 1] == ans) { cout << i << " "; } } cout << endl; return 0; }
|