题意: 一一个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
Source Code:
//#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-7 ; const int N = 210 ; const int M = 1100011*2 ; const ll P = 10000000097ll ; const int MAXN = 10900000 ; int dp[120][40][40][40], n, ans; char c; int GetValue (char c) { if (c >= '2' && c <= '9') { return c - '0'; } else { if (c == 'A') return 1; if (c == 'T') return 10; if (c == 'J') return 10; if (c == 'Q') return 10; if (c == 'K') return 10; if (c == 'F') return 0; } return 0; } int main(){ std::ios::sync_with_stdio(false); int i, j, t, k, u, v, g, numCase = 0; while (cin >> n) { if (0 == n) break; memset (dp, -1, sizeof (dp)); dp[0][0][0][0] = 0; ans = 0; for (i = 0; i <= n; ++i) { if (i < n) { cin >> c; } else { c = 0; } v = GetValue(c); for (j = 0; j < 31; ++j) { for (k = 0; k < 31; ++k) { for (g = 0; g < 31; ++g) { if (dp[i][j][k][g] == -1) continue; checkmax(ans, dp[i][j][k][g]); if ((v == 0 && j < 21) || j + v == 21) { checkmax(dp[i + 1][0][k][g], dp[i][j][k][g] + 150); } else if (j < 21) { checkmax(dp[i + 1][j + v][k][g], dp[i][j][k][g] + 50); } if ((v == 0 && k < 21) || k + v == 21) { checkmax(dp[i + 1][j][0][g], dp[i][j][k][g] + 250); } else if (k < 21) { checkmax(dp[i + 1][j][k + v][g], dp[i][j][k][g] + 50); } if ((v == 0 && g < 21) || g + v == 21) { checkmax(dp[i + 1][j][k][0], dp[i][j][k][g] + 350); } else if (g < 21) { checkmax(dp[i + 1][j][k][g + v], dp[i][j][k][g] + 50); } } } } memset (dp[i], -1, sizeof (dp[i])); } cout << ans << endl; } return 0; }