题意:

一一个21点游戏。

1. 有三个牌堆,分别为1X,2X,3X。

2. 纸牌A的值为1,纸牌2-9的值与牌面面相同,10(T)、J、Q、K的值为10,而而joke(F)的值为

任意大大。

3. 一一列牌要按顺序放入入三个牌堆中。当某个牌堆的值超过21点时,不能在放牌;如果某个牌堆的

总值为21点时,这个排队讲会被清空;joke放上后这个牌堆的值立立即变为21点。

4. 成功放上一一张牌得50美元;成功清空一一个牌堆讲得到100*牌堆号美元,即1X得100美元,2X得

200美元,3X得300美元。

5. 当任意一一堆都不能继续放牌,或者已经没牌时,游戏结束。

现在求一一列扑克牌通过某种方方式放最多能得多少美元。

思路:

四维DP,令dp[i][j][k][g]表示示放第i张牌时,1X堆的值为j,2X堆的值为k,3X的值为g时,最

多能拿到的钱。以1x为例,设v为当前牌的值,其转移方方程为 dp[i+1][j+v][k][g] =

max(dp[i+1][j+v][k][g], dp[i][j][k][g]+50),当 j < 21且 j + v != 21且 v !=

21 时。dp[i+1][0][k][g] = max(dp[i+1][0][k][g], dp[i][j][k][g]+50),当 j <

21且 v 为 joke,或者 j + v == 21。

当然可以利用用滚动数组降低空间消耗。

Solution by Sake

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

#include <stack>

#include <string>

#include <map>

#include <set>

#include <list>

#include <queue>

#include <vector>

#include <algorithm>

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

#define pi acos(-1.0)

using namespace std;

typedef long long           ll      ;

typedef unsigned long long  ull     ;

typedef unsigned int        uint    ;

typedef unsigned char       uchar   ;

template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}

template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}

const double eps = 1e-      ;

const int N =             ;

const int M = *      ;

const ll P = 10000000097ll   ;

const int MAXN =     ;

int dp[][][][], n, ans;

char c;

int GetValue (char c) {

    if (c >= '' && c <= '') {

        return c - '';

    } else {

        if (c == 'A')   return ;

        if (c == 'T')   return ;

        if (c == 'J')   return ;

        if (c == 'Q')   return ;

        if (c == 'K')   return ;

        if (c == 'F')   return ;

    }

    return ;

}

int main(){

    std::ios::sync_with_stdio(false);

    int i, j, t, k, u, v, g, numCase = ;

    while (cin >> n) {

        if ( == n) break;

        memset (dp, -, sizeof (dp));

        dp[][][][] = ;

        ans = ;

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

            if (i < n) {

                cin >> c;

            } else {

                c = ;

            }

            v = GetValue(c);

            for (j = ; j < ; ++j) {

                for (k = ; k < ; ++k) {

                    for (g = ; g < ; ++g) {

                        if (dp[i][j][k][g] == -)   continue;

                        checkmax(ans, dp[i][j][k][g]);

                        if ((v ==  && j < ) || j + v == ) {

                            checkmax(dp[i + ][][k][g], dp[i][j][k][g] + );

                        } else if (j < ) {

                            checkmax(dp[i + ][j + v][k][g], dp[i][j][k][g] + );

                        }

                        if ((v ==  && k < ) || k + v == ) {

                            checkmax(dp[i + ][j][][g], dp[i][j][k][g] + );

                        } else if (k < ) {

                            checkmax(dp[i + ][j][k + v][g], dp[i][j][k][g] + );

                        }

                        if ((v ==  && g < ) || g + v == ) {

                            checkmax(dp[i + ][j][k][], dp[i][j][k][g] + );

                        }  else if (g < ) {

                            checkmax(dp[i + ][j][k][g + v], dp[i][j][k][g] + );

                        }

                    }

                }

            }

            memset (dp[i], -, sizeof (dp[i]));

        }

        cout << ans << endl;

    }

    return ;

}