60pts求助
查看原帖
60pts求助
795344
crz_qwq楼主2024/11/20 10:51
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f,N=105;
int dp[N][N],f[N][N],a[N];
char op[N];
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>op[i]>>a[i];
        op[i+n]=op[i];
        a[i+n]=a[i];
        dp[i][i]=dp[i+n][i+n]=a[i];
        f[i][i]=f[i+n][i+n]=a[i];
    }
    for(int len=2;len<=n;++len)
    {
        for(int i=1;i+len-1<=n<<1;++i)
        {
            int j=i+len-1;
            dp[i][j]=-inf;
            if(op[i+1]=='t')
                dp[i][j]=max({dp[i+1][j]+a[i],f[i+1][j]+a[i],dp[i][j]});
            else if(op[i+1]=='x')
                dp[i][j]=max({dp[i+1][j]*a[i],f[i+1][j]*a[i],dp[i][j]});
            if(op[j]=='t')
                dp[i][j]=max({dp[i][j-1]+a[j],f[i][j-1]+a[j],dp[i][j]});
            else if(op[j]=='x')   
                dp[i][j]=max({dp[i][j-1]*a[j],dp[i][j],f[i][j-1]*a[j]});
            f[i][j]=inf;
            if(op[i+1]=='t')
                f[i][j]=min({dp[i+1][j]+a[i],f[i+1][j]+a[i],f[i][j]});
            else if(op[i+1]=='x')
                f[i][j]=min({dp[i+1][j]*a[i],f[i+1][j]*a[i],f[i][j]});
            if(op[j]=='t')
                f[i][j]=min({f[i][j-1]+a[j],dp[i][j-1]+a[j],f[i][j]});
            else if(op[j]=='x')
                f[i][j]=min({f[i][j-1]*a[j],dp[i][j-1]*a[j],f[i][j]});
        }
    }
    int ans=-inf;
    for(int i=1;i<=n;++i)
        ans=max(ans,dp[i][i+n-1]);
    cout<<ans<<'\n';
    for(int i=1;i<=n;++i)
        if(dp[i][i+n-1]==ans)
            cout<<i<<' ';
    cout<<'\n';
    return 0;
}
2024/11/20 10:51
加载中...