SPOJ 364 Pocket Money 简单DP

跟矩阵链乘同类型的题……

输出用%llu不是%I64u……

几组数据：

14
1+2*4+3*4+5*0
0*5*6+7*3+2
3+0+6+7+0+4
4*5+7*1*1+1
2*0+3*4*0+5*6+7+8
1+2+3*1+2*1+0
0+2*2+3*0+4
8*9*0+2
2*0+1+0*3
2*0*3+7+1*0*3
1+3*0*5+2
1+1+1+1+1
2*1+1+2*1+2*1+6
1*2*4*0*6*3

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cctype>

#include <algorithm>

#define LL unsigned long long int

using namespace std;

const int MAXN = ;

int cntNum, cntOp;

char str[MAXN];

char op[MAXN];

LL num[MAXN];

bool vis[MAXN][MAXN];

LL dpMax[MAXN][MAXN];

LL dpMin[MAXN][MAXN];

void show()

{

    printf("All nums: \n");

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

        printf( "%I64d ", num[i] );

    printf("\nAll Ops:\n");

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

        putchar( op[i] );

    puts("");

    return;

}

void chuli()

{

    cntNum = cntOp = ;

    int len = strlen(str);

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

    {

        LL tmp = ;

        while ( i < len && isdigit( str[i] ) )

        {

            tmp = tmp *  + ( str[i] - '' );

            ++i;

        }

        num[ cntNum++ ] = tmp;

        if ( i < len )

            op[ cntOp++ ] = str[i];

    }

    //show();

    return;

}

LL DPMAX( int l, int r )

{

    LL &res = dpMax[l][r];

    if ( vis[l][r] ) return res;

    vis[l][r] = true;

    if ( l == r ) return res = num[l];

    res = ;

    for ( int k = l; k < r; ++k )

    {

        if ( op[k] == '+' )

            res = max( res, DPMAX( l, k ) + DPMAX( k + , r ) );

        else if ( op[k] == '*' )

            res = max( res, DPMAX( l, k ) * DPMAX( k + , r ) );

    }

    //printf( "dp[%d][%d]=%I64u\n", l, r, res );

    return res;

}

LL DPMIN( int l, int r )

{

    LL &res = dpMin[l][r];

    if ( vis[l][r] ) return res;

    vis[l][r] = true;

    if ( l == r ) return res = num[l];

    bool first = true;

    for ( int k = l; k < r; ++k )

    {

        if ( op[k] == '+' )

        {

            if ( first )

            {

                res = DPMIN( l, k ) + DPMIN( k + , r );

                first = false;

            }

            else

                res = min( res, DPMIN( l, k ) + DPMIN( k + , r ) );

        }

        else if ( op[k] == '*' )

        {

            if ( first )

            {

                res = DPMIN( l, k ) * DPMIN( k + , r );

                first = false;

            }

            else

                res = min( res, DPMIN( l, k ) * DPMIN( k + , r ) );

        }

    }

    //printf( "dp[%d][%d]=%I64u\n", l, r, res );

    return res;

}

int main()

{

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%s", str );

        chuli();

        memset( dpMax, , sizeof(dpMax) );

        memset( dpMin, , sizeof(dpMin) );

        memset( vis, false, sizeof(vis) );

        LL maxx = DPMAX( , cntNum -  );

        memset( vis, false, sizeof(vis) );

        LL minn = DPMIN( , cntNum -  );

        printf( "%llu %llu\n", maxx, minn );

    }

    return ;

}

巴特西

SPOJ 364 Pocket Money 简单DP

最新文章

热门文章