一道稍微变型的区间DP模版,由于可能出现负数,那么最小值*最小值有可能变为最大值,因此需要记录一下最大值和最小值,再考虑状态的转移,删边就复制多一串就好了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N=105;
int f[2][N][N],a[N];char c[N];//0 max 1 min
int main()
{
int n;scanf("%d",&n);
memset(f[0],0xcf,sizeof(f[0]));
memset(f[1],0x3f,sizeof(f[1]));
for(int i=1;i<=n;i++)cin>>c[i],scanf("%d",&a[i]),c[i+n]=c[i],a[i+n]=a[i],f[1][i][i]=f[0][i][i]=f[1][i+n][i+n]=f[0][i+n][i+n]=a[i];
for(int k=2;k<=n;k++)
for(int l=1;l<=2*n-k+1;l++)
{
int r=l+k-1;
for(int mid=l+1;mid<=r;mid++)
if(c[mid]=='t')
{
f[0][l][r]=max(f[0][l][r],f[0][l][mid-1]+f[0][mid][r]);
f[1][l][r]=min(f[1][l][r],f[1][l][mid-1]+f[1][mid][r]);
}
else
{
f[0][l][r]=max(f[0][l][r],max(f[0][l][mid-1]*f[0][mid][r],f[1][l][mid-1]*f[1][mid][r]));
f[1][l][r]=min(f[1][l][r],min(f[0][l][mid-1]*f[0][mid][r],min(f[0][l][mid-1]*f[1][mid][r],min(f[1][l][mid-1]*f[0][mid][r],f[1][l][mid-1]*f[1][mid][r]))));
}
}
int ans=0xcfcfcfcf;
for(int i=1;i<=n;i++)
ans=max(ans,f[0][i][i+n-1]);
printf("%d\n",ans);
for(int i=1;i<=n;i++)if(f[0][i][i+n-1]==ans)printf("%d ",i);
puts("");
return 0;
}
最后一次更新于2019-10-25
0 条评论