POJ1179 Polygon

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

石子合并的升级版。有负值。但运算符只有 + 和 * 。

考虑负值对原做法正确性的影响：之所以仅记录最大值可能不对，是因为有可能负数 * 负数得到很大结果。

发现只有这种情况影响。而且这种情况中负数越小越优。所以记录一下最小值，每次参与更新就行了。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

//const int INF=16843009,FIN=-16843010;

int n,d[][][],ans=-;//别忘了ans的初值

char ch[];

int main()

{

    scanf("%d",&n);//初值？

    memset(d[],-,sizeof d[]);

    memset(d[],,sizeof d[]);

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

    {

        scanf(" %c%d",&ch[i],&d[][i][i]);

        d[][i][i]=d[][i][i];

        d[][i+n][i+n]=d[][i][i];d[][i+n][i+n]=d[][i][i];

        ch[i+n]=ch[i];

//        printf("(%d)(%c)",d[0][i][i],ch[i]);

    }

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

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

        {

            int r=l+i-;

            for(int k=l;k<r;k++)//l~k k+1~r

            {

                if(ch[k+]=='t')

                {

//                    printf("(%d+%d) ",d[0][k][k],d[0][k+1][k+1]);

                    d[][l][r]=max(d[][l][r],d[][l][k]+d[][k+][r]);

                    d[][l][r]=min(d[][l][r],d[][l][k]+d[][k+][r]);

                }

                if(ch[k+]=='x')

                {

//                    printf("(%d*%d) ",d[0][k][k],d[0][k+1][k+1]);

                    d[][l][r]=max(d[][l][r],max(d[][l][k]*d[][k+][r],d[][l][k]*d[][k+][r]));

                    d[][l][r]=min(min(d[][l][r],d[][l][k]*d[][k+][r])

                                        ,min(d[][l][k]*d[][k+][r],d[][l][k]*d[][k+][r]));

                }

            }

        }

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

        ans=max(ans,d[][i][i+n-]);

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

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

        if(d[][i][i+n-]==ans)

            printf("%d ",i);

    return ;

}