状态转移
区间变链, 在枚举z左右区间最值的运算四个值即可
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110, INF = 32768;
int n;
int w[N], f[N][N], g[N][N];
char c[N];
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> c[i] >> w[i];
w[i + n] = w[i];
c[i + n] = c[i];
}
for (int len = 1; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n * 2; l ++ )
{
int r = l + len - 1;
if (len == 1) f[l][r] = g[l][r] = w[l];
else
{
f[l][r] = -INF, g[l][r] = INF;
for (int k = l; k < r; k ++ )
{
char op = c[k + 1];
int minl = g[l][k], maxl = f[l][k];
int minr = g[k + 1][r], maxr = f[k + 1][r];
if (op == 't')
{
if (f[l][r] < (maxl + maxr)) f[l][r] = maxl + maxr;
if (g[l][r] > (minl + minr)) g[l][r] = minl + minr;
}
else
{
int a = minl * minr, b = minl * maxr;
int c = maxl * minr, d = maxl * maxr;
int e = g[l][r];
int cnt = (a < b ? (a < c ? (a < d ? (a < e ? a : e) : (d < e ? d : e)) : (c < d ? (c < e ? c : e) : (d < e ? d : e))) : (b < c ? (b < d ? (b < e ? b : e) : (d < e ? d : e)) : (c < d ? (c < e ? c : e) : (d < e ? d : e))));
if (g[l][r] > cnt) g[l][r] = cnt;
e = f[l][r];
cnt = (a > b ? (a > c ? (a > d ? (a > e ? a : e) : (d > e ? d : e)) : (c > d ? (c > e ? c : e) : (d > e ? d : e))) : (b > c ? (b > d ? (b > e ? b : e) : (d > e ? d : e)) : (c > d ? (c > e ? c : e) : (d > e ? d : e))));
if (f[l][r] < cnt) f[l][r] = cnt;
// f[l][r] = max({a, b, c, d, f[l][r]});
// g[l][r] = min({a, b, c, d, g[l][r]});
}
}
}
}
int res = -INF;
for (int i = 1; i <= n; i ++ )
if (res < f[i][i + n - 1])
res = f[i][i + n - 1];
cout << res << endl;
for (int i = 1; i <= n; i ++)
if (res == f[i][i + n - 1])
cout << i << " ";
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}