洛谷 P4342 [IOI1998]Polygon（区间DP）

题目链接：https://www.luogu.com.cn/problem/P4342

考虑断掉哪条边，可以将区间变成环，然后进行区间DP。

因为数据有负数，而两个负数（最小值）相乘可能是最大值，或者正数乘负数可能是最小值等情况。所以要保存最大值和最小值。

所以设f[i][j][0/1]表示[i,j]区间所能求得的最大/小值。DP后用ans记录长度为n的最大值。然后再扫一遍，如果有长度为n的最大值等于ans，则将i都输出。

AC代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n;
const int N=105;
char op[N];
int a[N];
int f[N][N][2],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>op[i]>>a[i];
        a[i+n]=a[i]; op[i+n]=op[i];
    }
    for(int i=1;i<=2*n;i++)
    for(int j=1;j<=2*n;j++) f[i][j][0]=-0x3f3f3f3f,f[i][j][1]=0x3f3f3f3f;
    for(int i=1;i<=2*n;i++) f[i][i][0]=f[i][i][1]=a[i];
    for(int l=1;l<=n;l++)
    for(int i=1;i<=2*n;i++){
        int j=i+l;
        if(j>2*n) break;
        for(int k=i+1;k<=j;k++){
            if(op[k]=='x'){
                f[i][j][0]=max(f[i][j][0],max(f[i][k-1][0]*f[k][j][0],f[i][k-1][1]*f[k][j][1]));
                f[i][j][1]=min(f[i][j][1],min(f[i][k-1][0]*f[k][j][1],min(f[i][k-1][1]*f[k][j][0],f[i][k-1][1]*f[k][j][1])));
            }
            else{
                f[i][j][0]=max(f[i][j][0],f[i][k-1][0]+f[k][j][0]);
                f[i][j][1]=min(f[i][j][1],f[i][k-1][1]+f[k][j][1]);
            }
        }
    }
    for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1][0]); printf("%d
",ans);
    for(int i=1;i<=n;i++) if(f[i][i+n-1][0]==ans) printf("%d ",i);
    return 0;
}