luogu P4342 [IOI1998]Polygon

IOISo many DP in the early days?

The title requires that one side of the ring be broken. We can break the link into a chain and open a two fold array.

Easy to think of DP, set up\(f_{i,j}\)For interval\([i,j]\)The maximum value is then the interval DP of an enumeration breakpoint.

But there may be negative numbers, which means that there may be two negative numbers in the interval multiply to get the maximum, so let’s say\(g_{i,j}\)For interval\([i,j]\)Minimum value

When transferring, consider all possible situations.

// 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;
}