[P4342][IOI1998] Polygon (区间DP)

题意：给定一个多边形，每个顶点上都有数字，任意两个顶点之间的边都有一个符号（+，×），每删掉一条边，就可以让该边的两个顶点通过该边的运算符号来计算得到一个新的顶点，求一个删边策略使得最终剩下一个点时，该点数值最大，并输出删掉的第一条边能得到最大值的序号；

解法：区间DP；

1.区间DP；先断环为链，然后就可以进行常规的区间DP操作了，但是在转移的时候要注意了，因为点上的值可能为附数，所以两个最小值（负数）相乘可能比两个最大值（整正）相乘还要大，所以我们要设两个DP方程；

设 f[i][j][0]表示合并了 i~j的最大值，f[i][j][1]表示合并了 i~j的最小值；

枚举中间点 k，若 op[k+1]为正号，则有：f[i][j][0]=max(f[i][j][0],f[i][k][0]+f[k+1][j][0]);   f[i][j][1]=min(f[i][j][1],f[i][k][1]+f[k+1][j][1]);

否则：f[i][j][0]=max(f[i][j][0],max(f[i][k][0]*f[k+1][j][0],max(f[i][k][1]*f[k+1][j][1],max(f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]))));

           f[i][j][1]=min(f[i][j][1],min(f[i][k][1]*f[k+1][j][1],min(f[i][k][0]*f[k+1][j][0],min(f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]))));

附上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 150;
const int inf = 0x7f7f7f7f;

int n;
int a[N*2],f[N][N][3],ans;
char op[N*2];

int main()
{
    cin>>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]=-inf,f[i][j][1]=inf;
    for(int i=1;i<=2*n;++i) f[i][i][0]=f[i][i][1]=a[i];
    for(int len=2;len<=n;++len){
        for(int i=1,j=len;j<=2*n;i++,j++){
            for(int k=i;k<j;++k){
                if(op[k+1]=='x'){//在存储的时候，是先存边在存点的，所以要 +1 
                    f[i][j][0]=max(f[i][j][0],max(f[i][k][0]*f[k+1][j][0],max(f[i][k][1]*f[k+1][j][1],max(f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]))));
                    f[i][j][1]=min(f[i][j][1],min(f[i][k][1]*f[k+1][j][1],min(f[i][k][0]*f[k+1][j][0],min(f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]))));
                }
                else {
                    f[i][j][0]=max(f[i][j][0],f[i][k][0]+f[k+1][j][0]);
                    f[i][j][1]=min(f[i][j][1],f[i][k][1]+f[k+1][j][1]);
                }
            }
        }
    }
    for(int i=1;i<=n;++i) ans=max(ans,f[i][i+n-1][0]);
    printf("%d\n",ans);
    for(int i=1;i<=n;++i)
        if(f[i][i+n-1][0]==ans) printf("%d ",i);//只要 f[i][i+n-1][0]==ans，就说明以 i为第一条删的边的策略可以达到最大值，所以直接输出 i就行了 
    return 0;
}