[题目链接]
[算法]
搜索，对于每一种状态，我们可以将其压缩成一个五进制数，用STL-map记录在其状态下的最少出牌次数
在搜索时，我们可以采取一个优化 : 如果只剩下单牌，那么直接将单牌出完
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 25 #define MAXT 10 #define MAXC 15 const int inf = 2e9; int T,n; int cnt[MAXC + 1]; map<long long,int> mp; inline long long get_state() { long long ret = 0; for (int i = 1; i <= 15; i++) ret = 1ll * ret * 5 + 1ll * cnt[i]; return ret; } inline int dfs() { int step = inf; long long state = get_state(); bool flag = false; if (state == 0) return 0; if (mp.count(state)) return mp[state]; for (int i = 1; i <= 11; i++) { if (cnt[i] >= 3 && cnt[i + 1] >= 3) { for (int j = i + 1; j <= 12; j++) { if (cnt[j] >= 3) { for (int k = i; k <= j; k++) cnt[k] -= 3; step = min(step,dfs() + 1); flag = true; for (int k = i; k <= j; k++) cnt[k] += 3; } else break; } } } for (int i = 1; i <= 10; i++) { if (cnt[i] >= 2 && cnt[i + 1] >= 2 && cnt[i + 2] >= 2) { for (int j = i + 2; j <= 12; j++) { if (cnt[j] >= 2) { for (int k = i; k <= j; k++) cnt[k] -= 2; step = min(step,dfs() + 1); flag = true; for (int k = i; k <= j; k++) cnt[k] += 2; } else break; } } } for (int i = 1; i <= 8; i++) { if (cnt[i] >= 1 && cnt[i + 1] >= 1 && cnt[i + 2] >= 1 && cnt[i + 3] >= 1 && cnt[i + 4] >= 1) { for (int j = i + 4; j <= 12; j++) { if (cnt[j] >= 1) { for (int k = i; k <= j; k++) cnt[k]--; flag = true; step = min(step,dfs() + 1); for (int k = i; k <= j; k++) cnt[k]++; } else break; } } } for (int i = 1; i <= 13; i++) { if (cnt[i] >= 4) { cnt[i] -= 4; for (int j = 1; j <= 15; j++) { if (!cnt[j]) continue; cnt[j]--; for (int k = 1; k <= 15; k++) { if (!cnt[k]) continue; cnt[k]--; flag = true; step = min(step,dfs() + 1); cnt[k]++; } cnt[j]++; } for (int j = 1; j <= 15; j++) { if (cnt[j] < 2) continue; cnt[j] -= 2; for (int k = 1; k <= 15; k++) { if (cnt[k] < 2) continue; cnt[k] -= 2; flag = true; step = min(step,dfs() + 1); cnt[k] += 2; } cnt[j] += 2; } cnt[i] += 4; } } for (int i = 1; i <= 13; i++) { if (cnt[i] >= 3) { cnt[i] -= 3; for (int j = 1; j <= 13; j++) { if (cnt[j] >= 2) { cnt[j] -= 2; flag = true; step = min(step,dfs() + 1); cnt[j] += 2; } } cnt[i] += 3; } } for (int i = 1; i <= 13; i++) { if (cnt[i] >= 3) { cnt[i] -= 3; for (int j = 1; j <= 15; j++) { if (cnt[j] >= 1) { cnt[j]--; flag = true; step = min(step,dfs() + 1); cnt[j]++; } } cnt[i] += 3; } } for (int i = 1; i <= 13; i++) { if (cnt[i] >= 4) { cnt[i] -= 4; flag = true; step = min(step,dfs() + 1); cnt[i] += 4; } } for (int i = 1; i <= 13; i++) { if (cnt[i] >= 3) { cnt[i] -= 3; flag = true; step = min(step,dfs() + 1); cnt[i] += 3; } } for (int i = 1; i <= 13; i++) { if (cnt[i] >= 2) { cnt[i] -= 2; flag = true; step = min(step,dfs() + 1); cnt[i] += 2; } } if (cnt[14] >= 1 && cnt[15] >= 1) { cnt[14]--; cnt[15]--; flag = true; step = min(step,dfs() + 1); cnt[14]++; cnt[15]++; } if (!flag) { step = 0; for (int i = 1; i <= 15; i++) step += cnt[i]; } return mp[state] = step; } int main() { scanf("%d%d",&T,&n); mp.clear(); while (T--) { memset(cnt,0,sizeof(cnt)); for (int i = 1; i <= n; i++) { int a,b; scanf("%d%d",&a,&b); if (a == 0 && b == 1) cnt[14]++; else if (a == 0 && b == 2) cnt[15]++; else if (a == 2) cnt[13]++; else if (a == 1) cnt[12]++; else cnt[a - 2]++; } printf("%d ",dfs()); mp.clear(); } return 0; }