poj1179多边形——区间DP

题目：http://poj.org/problem?id=1179

区间DP，值得注意的是有负值，而且有乘法，因此可能会影响最大值；

注意memset中写-1仅仅是-1，-2才是一个很小的负数；

最后找mxx时也要注意可能最大是负值，因此不能随便给mxx赋成0或-1之类。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,a[],mx[][],mn[][],ans[],t,INF=;

bool sid[][];

int main()

{

    char dc;

    scanf("%d ",&n);

    memset(mx,-,sizeof mx);//-1仅是-1！

    memset(mn,,sizeof mn);

    for(int i=;i<=n;i++)

    {

        if(i==n)scanf("%c %d",&dc,&a[i]);

        else scanf("%c %d ",&dc,&a[i]);

        if(dc=='t')sid[i-][i]=;

        else sid[i-][i]=;

        a[i+n]=a[i];

        sid[i-+n][i+n]=sid[i-][i];

        mx[i][i]=a[i];mx[i+n][i+n]=a[i];

        mn[i][i]=a[i];mn[i+n][i+n]=a[i];

    }

    for(int l=;l<=n;l++)

        for(int i=;i<=n*-l;i++)//

        {

            int j=i+l-;

            for(int k=i;k<j;k++)

            {

                if(sid[k][k+])

                {

                    mx[i][j]=max(mx[i][j],mx[i][k]+mx[k+][j]);

                    mn[i][j]=min(mn[i][j],mn[i][k]+mn[k+][j]);

                }

                else

                {

                    mx[i][j]=max(mx[i][j],mx[i][k]*mx[k+][j]);

                    mx[i][j]=max(mx[i][j],mn[i][k]*mn[k+][j]);

                    mx[i][j]=max(mx[i][j],mx[i][k]*mn[k+][j]);

                    mx[i][j]=max(mx[i][j],mn[i][k]*mx[k+][j]);

                    mn[i][j]=min(mn[i][j],mx[i][k]*mx[k+][j]);

                    mn[i][j]=min(mn[i][j],mn[i][k]*mn[k+][j]);

                    mn[i][j]=min(mn[i][j],mx[i][k]*mn[k+][j]);

                    mn[i][j]=min(mn[i][j],mn[i][k]*mx[k+][j]);

                }

            }

        }

    int mxx=-INF;//!-1

//    for(int i=1;i<=n;i++)

//    {

//        if(mx[i][i+n-1]>mxx)

//        {

//            memset(ans,0,sizeof ans);

//            t=1;

//            ans[t]=i;

//            mxx=mx[i][i+n-1];

//        }

//        else if(mx[i][i+n-1]==mxx)ans[++t]=i;

//    }

//    printf("%d\n",mxx);

//    for(int i=1;i<=t;i++)

//        printf("%d ",ans[i]);

    for(int i=;i<=n;i++)

        mxx=max(mxx,mx[i][i+n-]);

    printf("%d\n",mxx);

    for(int i=;i<=n;i++)

        if(mx[i][i+n-]==mxx)

            printf("%d ",i);

    return ;

}