[C++知识库]acwing 283

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;
char s[60];
int a[60];
int f[60][60][2];


signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> s[i] >> a[i];
    
    vector<int> ans;
    int res = INT_MIN;
    
    for (int p = 1; p <= n; p ++)
    {
        vector<int> ta;
        vector<char> ts;
        ta.push_back(0);
        ts.push_back('1');
        for (int i = p + 1; i <= n; i ++) ts.push_back(s[i]);
        for (int i = 1; i <= p - 1; i ++) ts.push_back(s[i]);
        for (int i = p; i <= n; i ++) ta.push_back(a[i]);
        for (int i = 1; i <= p - 1; i ++) ta.push_back(a[i]);
        
        for (int i = 0; i<= n+5; i ++)
            for (int j = 0; j <= n+5; j ++) f[i][j][0] = -0x3f3f3f3f;
        
        for (int i = 0; i<= n+5; i ++)
            for (int j = 0; j <= n+5; j ++) f[i][j][1] = 0x3f3f3f3f;
            
        for (int x = 0; x <= 1; x ++) 
            for (int i = 1; i <= n; i ++) f[i][i][x] = ta[i];
        
        for (int k = 2; k <= n; k ++)
            for (int l = 1; l <= n - k + 1; l ++)
            {
                int en = l + k - 1;
                for (int e = l; e < en; e ++)
                {
                    if (ts[e] == 't')
                        {
                            f[l][en][0] = max(f[l][en][0], f[l][e][0] + f[e+1][en][0]);
                            f[l][en][1] = min(f[l][en][1], f[l][e][1] + f[e+1][en][1]);
                        }
                    else
                        {
                            for (int x = 0; x <= 1; x ++)
                                for (int y = 0; y <= 1; y ++)
                                {
                                    f[l][en][0] = max(f[l][en][0], f[l][e][x] * f[e+1][en][y]);
                                    f[l][en][1] = min(f[l][en][1], f[l][e][x] * f[e+1][en][y]);
                                }
                        }
                }
            }
        
        if (f[1][n][0] > res)
        {
            ans.clear();
            ans.push_back(p);
            res = f[1][n][0];
        }
        else if (f[1][n][0] == res)
            ans.push_back(p);
        
    }
    
    cout << res << endl;
    for (int v : ans) cout << v << " ";
    cout << endl;
    return 0;
}