luogu P4342 [IOI1998]Polygon

时间:2023-01-16 10:34:21

IOI早期这么多dp?

题目要求断掉环上的一边,我们可以断环为链,开两倍数组

容易想到dp,设\(f_{i,j}\)为区间\([i,j]\)的最大值,然后就是个枚举断点的区间dp

不过可能会有负数出现,这意味着可能区间中可能会有两个负数相乘得到最大值的情况,所以设\(g_{i,j}\)为区间\([i,j]\)的最小值

转移时记得考虑所有可能情况

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b)) using namespace std;
const int N=100+10;
const LL inf=1e14;
il LL rd()
{
re LL x=0,w=1;re char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
LL f[N][N],g[N][N],ans=-inf,an[N],a[N][2],tt;
int n,m; int main()
{
n=rd();
for(int i=1;i<=n;i++)
{
char cc[2];
scanf("%s",cc);
a[i][1]=a[i+n][1]=(cc[0]=='t');
a[i][0]=a[i+n][0]=f[i][i]=f[i+n][i+n]=g[i][i]=g[i+n][i+n]=rd();
}
for(int l=1;l<=n-1;l++)
for(int i=1,j=i+l;j<(n<<1);i++,j++)
{
f[i][j]=-inf,g[i][j]=inf;
for(int k=i+1;k<=j;k++)
{
if(a[k][1])
f[i][j]=max(f[i][j],f[i][k-1]+f[k][j]),
g[i][j]=min(g[i][j],g[i][k-1]+g[k][j]);
else
f[i][j]=max(f[i][j],max(f[i][k-1]*f[k][j],g[i][k-1]*g[k][j])),
g[i][j]=min(g[i][j],min(f[i][k-1]*f[k][j],g[i][k-1]*g[k][j])),
g[i][j]=min(g[i][j],min(f[i][k-1]*g[k][j],g[i][k-1]*f[k][j]));
}
//printf("%d %d %lld %lld\n",i,j,f[i][j],g[i][j]);
}
for(int i=1;i<=n;i++)
if(ans<f[i][i+n-1]) ans=f[i][i+n-1],an[tt=1]=i;
else if(ans==f[i][i+n-1]) an[++tt]=i;
printf("%lld\n",ans);
for(int i=1;i<=tt;i++) printf("%lld ",an[i]);
return 0;
}