求救
查看原帖
求救
1024213
albertting楼主2024/4/4 11:12
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

char ch[105];
int n, a[105], dpmx[105][105], dpmn[105][105], maxn = -inf;

int main()
{
    scanf("%d\n", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%c %d", &ch[i], &a[i]);
        getchar();
        ch[i + n] = ch[i];
        a[i + n] = a[i];
        dpmx[i][i] = dpmn[i][i] = a[i];
    }
    for(int i = 1; i <= n * 2; i++)
        for(int j = 1; j <= n * 2; j++)
            if(i != j)
                dpmx[i][j] = -inf, dpmn[i][j] = inf;
    for(int d = 2; d <= n; d++)
        for(int i = 1; i <= 2 * n - d + 1; i++)
        {
            int j = i + d - 1;
            for(int k = i; k <= j; k++)
                if(ch[k + 1] == 't')
                {
                    dpmx[i][j] = max(dpmx[i][j],
                                     dpmx[i][k] + dpmx[k + 1][j]);
                    dpmn[i][j] = min(dpmn[i][j],
                                     dpmn[i][k] + dpmn[k + 1][j]);
                }
                else
                {
                    dpmx[i][j] = max(dpmx[i][j],
                                 max(dpmx[i][k] * dpmx[k + 1][j],
                                     dpmn[i][k] * dpmn[k + 1][j]));
                    dpmn[i][j] = min(dpmn[i][j],
                                 min(dpmn[i][k] * dpmn[k + 1][j],
                                 min(dpmx[i][k] * dpmn[k + 1][j],
                                     dpmn[i][k] * dpmx[k + 1][j])));
                }
        }
    for(int i = 1; i <= n; i++) maxn = max(maxn, dpmx[i][i + n - 1]);
    printf("%d\n", maxn);
    for(int i = 1; i <= n; i++)
        if(dpmx[i][i + n - 1] == maxn)
            printf("%d ", i);
    return 0;
}

RT,玄亿关

2024/4/4 11:12
加载中...