【题意】按照斗地主出牌规则，给定手牌求出完的最少步数。
【算法】模拟+搜索
【题解】
可以发现除了顺子，其它的出牌规则都和点数无关，只与同点数的牌数有关。
所以可以先暴力枚举要出哪些顺子，然后每一个出完顺子后手牌的情况处理成b[4]表示牌数为1~4的点数有多少个，然后进行dfs。（为了方便，将A接在14，然后注意2不能顺）
dfs(s,t,j,z)表示有s组牌数为1，有t组牌数为2，有j组牌数为3，有z组牌数为4的情况出完手牌的最少步数。（可以记忆化）
然后在dfs讨论一下【单打】【拆牌】【带牌】三种情况，对应转移就可以了。（数据小，写多暴力都没关系）
双王在进入dfs前特殊处理：有双王就考虑多一种当炸弹打的情况，然后就直接将王当作单排进入dfs。
代码已通过各大OJ增强版(>w<)。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=30,inf=0x3f3f3f3f; const int limit[5]={0,5,3,2}; int f[maxn][maxn][maxn][maxn],a[maxn],b[maxn]; int min(int a,int b){return a<b?a:b;} int dfs(int s,int t,int j,int z){ if(~f[s][t][j][z])return f[s][t][j][z]; int ans=inf; if(t)ans=min(ans,dfs(s+2,t-1,j,z)); if(j)ans=min(ans,dfs(s+1,t+1,j-1,z)); if(z)ans=min(ans,min(dfs(s,t+2,j,z-1),dfs(s+1,t,j+1,z-1))); if(j&&s)ans=min(ans,dfs(s-1,t,j-1,z)+1); if(j&&t)ans=min(ans,dfs(s,t-1,j-1,z)+1); if(z&&s>1)ans=min(ans,dfs(s-2,t,j,z-1)+1); if(z&&t>1)ans=min(ans,dfs(s,t-2,j,z-1)+1); return f[s][t][j][z]=min(ans,s+t+j+z); } int calc(int step){ int ans=inf,tot; for(int k=1;k<=3;k++){ for(int i=3;i<=14;i++){ tot=0; for(int j=i;j<=14;j++)if(a[j]>=k)tot++;else break; for(int j=i+limit[k]-1;j<=i+tot-1;j++){ for(int l=i;l<=j;l++)a[l]-=k; ans=min(ans,calc(step+1)); for(int l=i;l<=j;l++)a[l]+=k; } } } b[1]=b[2]=b[3]=b[4]=0; for(int i=2;i<=14;i++)b[a[i]]++; if(a[0]==2)ans=min(ans,step+1+dfs(b[1],b[2],b[3],b[4])); b[1]+=a[0]; ans=min(ans,step+dfs(b[1],b[2],b[3],b[4])); return ans; } int main(){ int T,n; scanf("%d%d",&T,&n); memset(f,-1,sizeof(f)); f[0][0][0][0]=0; while(T--){ int u,v; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ scanf("%d%d",&u,&v); a[u]++; } a[14]=a[1]; printf("%d ",calc(0)); } return 0; }//thanks for Lucius's code!