题解 P2540 【斗地主增强版】

这里提供一个双搜索的方法 第一个：搜索顺子（我的dfs函数） 第二个：记忆化搜索，没有顺子最多出几次（我的dfs2）（有人用贪心或dp做的） 代码ugly，dalao不要喷 ```cpp #include<bits/stdc++.h> using namespace std; #define MAXN 31 #define INF 0x3f3f3f3f int a[MAXN],b[MAXN],t[MAXN]; int n,m,ans = INF; int c[MAXN]; int f[24][24][24][24]; int dfs2(int i,int j,int k,int l)//i个4，j个3，k个2，l个1 { if(i<0||j<0||k<0||l<0) return INF;//出界无解，返回无穷 if(f[i][j][k][l] != 0) return f[i][j][k][l]; int r = i+j+k+l; r = min(r,dfs2(i-1,j,k,l-2)+1);//4&2 r = min(r,dfs2(i-1,j,k-1,l)+1);//4&2(1:2 2:2) r = min(r,dfs2(i-1,j-1,k,l+1)+1);//4&2(1:3 2:3) r = min(r,dfs2(i-1,j,k-2,l)+1);//4&2*2 r = min(r,dfs2(i-1,j-1,k-1,l+1)+1);//4&2*2 r = min(r,dfs2(i-2,j,k,l)+1);//4&2*2 r = min(r,dfs2(i-1,j+1,k,l+1));//手动拆弹 r = min(r,dfs2(i,j-1,k-1,l)+1);//3&2 r = min(r,dfs2(i,j-2,k,l+1)+1);//3&2 r = min(r,dfs2(i,j-1,k,l-1)+1);//3&1 r = min(r,dfs2(i,j-1,k-1,l+1)+1);//3&1 r = min(r,dfs2(i,j-2,k+1,l)+1);//3&1 f[i][j][k][l] = r; return r; } int tx() { memset(c,0,sizeof(c)); int ans = 0; int k = 0; for(int i = 1;i <= 13;i ++) c[t[i]] ++; k = t[14] + t[15];//王的数量 if(k == 0) return dfs2(c[4],c[3],c[2],c[1]); if(k == 1) return dfs2(c[4],c[3],c[2],c[1]+1); if(k == 2) return min(dfs2(c[4],c[3],c[2],c[1]+2),dfs2(c[4],c[3],c[2],c[1])+1); } const int fz[4] = {0,5,3,2}; int sd[105]; void dfs(int x) { if(x > ans) return; int o = tx(); int p = 0; int l = 0,j; if(x + o < ans) ans = x + o; for(int ss = 1; ss <= 3; ss ++) { for(int i = 3; i <= 15 - fz[ss]; i ++) { p = 1; j = i; if(t[i] >= ss) { while(1) { j ++; if(j > 13) l = 1; else l = j; if(j == 15) break; p ++; if(t[l] < ss) { p --; break; } } } if(p >= fz[ss]) { for(int j = i; j <= i + fz[ss] - 1; j ++){ if(j > 13) l = 1; else l = j; t[l] -= ss; } dfs(x+1); for(int j = i+fz[ss]; j <= i+p-1; j ++){ if(j > 13) l = 1; else l = j; t[l] -= ss; dfs(x + 1); } for(int j = i; j <= i + p-1; j ++){ if(j > 13) l = 1; else l = j; t[l] += ss; } } } } } int main() { scanf("%d%d",&m,&n); for(int tt = 1; tt <= m; tt ++) { ans = INF; memset(t,0,sizeof(t)); for(int i = 1; i <= n; i ++) { scanf("%d%d",&a[i],&b[i]); if(a[i] != 0) { t[a[i]] ++; } else t[13+b[i]] ++; } dfs(0); printf("%d\n",ans); } return 0; } ```