spoj 364

动规 f[i][j]表示第i到第j个数能取到的最大值 e[i][j]表示最小值 .......
#include <cstdio>

#include <cstring>

using namespace std;

char a[110];

int d[110];

bool c[110];

long long f[110][110],e[110][110];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(c, 0, sizeof(c));

        scanf("%s",a);

        int len = strlen(a);

        int u = 0;

        for(int i = 0; i < len; i += 2)

        {

            d[u] = a[i] - '0';

            if(a[i+1] == '+')

                c[u] = 1;

            u++;

        }

        for(int i = 0; i < u; i++)

            e[i][i] = f[i][i] = d[i];

        for(int q = 1; q < u; q++)

            for(int i = 0; i+q < u; i++)

            {

                int j = i+q;

                f[i][j] = 0;

                e[i][j] = (long long)1 << 62;

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

                {

                    long long p;

                    if(c[k])

                        p = f[i][k] + f[k+1][j];

                    else

                        p = f[i][k] * f[k+1][j];

                    if(f[i][j] < p)

                        f[i][j] = p;

                    if(c[k])

                        p = e[i][k] + e[k+1][j];

                    else

                        p = e[i][k] * e[k+1][j];

                    if(e[i][j] > p)

                        e[i][j] = p;

                }

            }

        printf("%lld %lld\n",f[0][u-1],e[0][u-1]);

    }

    return 0;

}
巴特西

spoj 364

最新文章

热门文章
