Deck of Cards ZOJ - 2852 dp 多决策 三维 滚动更新

题意：一个特殊21点游戏 具体http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2852

题解：建一个三维dp，表示三个卡槽分别为i,j,l分时最大的收益情况。

　　　　对所有当前状态dp，将下一个可能的状态存入f，

坑：~-1==0

#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<string>
#include<stack>
#include<ctime>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<sstream>
#include<fstream>
#include<iostream>
#include<functional>
#include<algorithm>
#include<memory.h>
//#define INF 0x3f3f3f3f
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
#define rep(i,t,n)  for(int i =(t);i<=(n);++i)
#define per(i,n,t)  for(int i =(n);i>=(t);--i)
#define mp make_pair
#define pb push_back
#define mmm(a,b) memset(a,b,sizeof(a))
//std::ios::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
void smain();
#define ONLINE_JUDGE
int main() {
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    FILE *myfile;
    myfile =freopen("C:\\Users\\SuuTT\\Desktop\\test\\in.txt", "r", stdin);
    if (myfile == NULL)
        fprintf(stdout, "error on input freopen\n");
    /*FILE *outfile;
    outfile= freopen("C:\\Users\\SuuTT\\Desktop\\test\\out.txt", "w", stdout);
    if (outfile == NULL)
        fprintf(stdout, "error on output freopen\n");*/
    long _begin_time = clock();
#endif
    smain();
#ifndef ONLINE_JUDGE
    long _end_time = clock();
    printf("time = %ld ms.", _end_time - _begin_time);
#endif
    return 0;
}
int dir[4][2] = { 1,0,0,1,-1,0,0,-1 };
const int maxn = 2e2 + 5;
int f[22][22][22], dp[22][22][22];

int n; int ans;
int num(char c) {
    if (c >= '0'&&c <= '9')return c - '0';
    else if (c == 'A')return 1;
    else if (c == 'F')return -1;
    else return 10;
}

void smain() {
    while (cin >> n) {
        if (n == 0)break;
        mmm(f, 0); mmm(dp, 0);
        string c;
        cin >> c;
        int x = num(c[0]);
        if (x==-1) {
            //cout << ~x << endl;
            dp[0][0][0] = 350;
            ans = 350;
        }
        else {
            dp[x][0][0] = 50;
            dp[0][x][0] = 50;
            dp[0][0][x] = 50;
            ans = 50;
        }
        rep(i, 2, n) {
            string c;
            cin >> c;
            int x = num(c[0]);
            rep(j, 0, 21)rep(k, 0, 21)rep(l, 0, 21) if(dp[j][k][l]){
                int t = dp[j][k][l];
                if ((x == -1 && j < 21) || x + j == 21) f[0][k][l] = max(f[0][k][l], t + 150);//放第一组//正好21，[j][k][l]->[0][k][l]
                else if (x + j < 21)f[j + x][k][l] = max(f[x + j][k][l], t + 50);//没到21[j][k][l]->[x + j][k][l]
                else if (x + j > 21 && j < 21)f[21][k][l] = max(f[21][k][l], t + 50);//超了21[j][k][l]->[21][k][l]
                
                if ((x == -1 && k < 21) || x + k == 21) { f[j][0][l] = max(f[j][0][l], t + 250); }
                else if (x + k < 21)f[j][k+x][l] = max(f[j][k+x][l], t + 50);
                else if (x + k > 21 && k < 21)f[j][21][l] = max(f[j][21][l], t + 50);

                if ((x == -1 && l < 21) || x + l == 21) { f[j][k][0] = max(f[j][k][0], t + 350); }
                else if (x + l < 21)f[j][k][l+x] = max(f[j][k][l+x], t + 50);
                else if (x + l > 21 && l < 21)f[j][k][21] = max(f[j][k][21], t + 50);
            }
            rep(j, 0, 21)rep(k, 0, 21)rep(l, 0, 21)dp[j][k][l] = f[j][k][l], ans = max(ans,dp[j][k][l]), f[j][k][l] = 0;
        }
        cout << ans << endl;
    }
    
}