题目：https://www.luogu.org/problemnew/show/P2540
发现如果没有顺子，剩下的可以贪心。所以搜索顺子怎么出，然后贪心。
这样只能过不加强版。原因是贪心的时候难以弄3=1+2。3应该是 3带* 还是拆开让4带上？
如这个数据（×后面是个数）：3×3，4×1，6×4，7×3，9×1，10×2，11×1，12×4，13×3
正解应该是把一个3拆成1+2，然后两次4带2，两次3带2。但贪心似乎做不了。
所以应该dp！记录1，2，3，4，王各有几个，就能把“拆”体现在状态转移里了。
自己以“还剩几张牌”为阶段，“拆”就是同层转移了；所以需要注意枚举的顺序，保证先同层转移到自己，再从自己转移。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=30,M=20; int T,n,a[N][M],nm[5],dp[N][N>>1][N/3][N>>2][3],fg,ans; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } void Mn(int &x,int y){x=min(x,y);} void calc(int cr) { memset(dp,0x3f,sizeof dp); memset(nm,0,sizeof nm); for(int i=1;i<=13;i++)nm[a[cr][i]]++; dp[nm[1]][nm[2]][nm[3]][nm[4]][fg]=0; int lm1=n,lm2=n>>1,lm3=n/3,lm4=(n>>2); for(int sm=nm[1]+(nm[2]<<1)+nm[3]*3+(nm[4]<<2)+fg;sm>=0;sm--) for(int l=lm4;l>=0;l--) for(int k=lm3;k>=0;k--) for(int j=lm2;j>=0;j--) for(int t=0;t<=2;t++) { int i=sm-(j<<1)-k*3-(l<<2)-t; if(i<0)continue; int d=dp[i][j][k][l][t]; if(d>n-cr)continue; if(l)Mn(dp[i+1][j][k+1][l-1][t],d);//4=1+3 if(l)Mn(dp[i][j+2][k][l-1][t],d);//4=2+2 if(k)Mn(dp[i+1][j+1][k-1][l][t],d);//3=1+2 if(j)Mn(dp[i+2][j-1][k][l][t],d);//2=1+1 d++; if(l&&i>=2)Mn(dp[i-2][j][k][l-1][t],d); if(l&&i&&t)Mn(dp[i-1][j][k][l-1][t-1],d); if(l&&t>=2)Mn(dp[i][j][k][l-1][0],d); if(l&&j>=2)Mn(dp[i][j-2][k][l-1][t],d); if(k&&j)Mn(dp[i][j-1][k-1][l][t],d); if(k&&i)Mn(dp[i-1][j][k-1][l][t],d); if(k&&t)Mn(dp[i][j][k-1][l][t-1],d); if(i)Mn(dp[i-1][j][k][l][t],d); if(j)Mn(dp[i][j-1][k][l][t],d); if(k)Mn(dp[i][j][k-1][l][t],d); if(l)Mn(dp[i][j][k][l-1][t],d); if(t==1)Mn(dp[i][j][k][l][t-1],d); if(t==2)Mn(dp[i][j][k][l][0],d); } ans=min(ans,cr+dp[0][0][0][0][0]); } void solve(int cr) { if(cr>ans)return; memcpy(a[cr],a[cr-1],sizeof a[cr-1]); for(int i=1,j;i<=11;i++) if(a[cr][i]>=3&&a[cr][i+1]>=3) { a[cr][i]-=3; for(j=i+1;j<=12&&a[cr][j]>=3;j++) a[cr][j]-=3; for(j--;j>=i+1;j--) solve(cr+1),a[cr][j]+=3; a[cr][i]+=3; } for(int i=1,j;i<=10;i++) if(a[cr][i]>=2&&a[cr][i+1]>=2&&a[cr][i+2]>=2) { a[cr][i]-=2;a[cr][i+1]-=2; for(j=i+2;j<=12&&a[cr][j]>=2;j++) a[cr][j]-=2; for(j--;j>=i+2;j--) solve(cr+1),a[cr][j]+=2; a[cr][i+1]+=2;a[cr][i]+=2; } for(int i=1,j;i<=8;i++) if(a[cr][i]&&a[cr][i+1]&&a[cr][i+2]&&a[cr][i+3]&&a[cr][i+4]) { a[cr][i]--;a[cr][i+1]--;a[cr][i+2]--;a[cr][i+3]--; for(j=i+4;j<=12&&a[cr][j];j++) a[cr][j]--; for(j--;j>=i+4;j--) solve(cr+1),a[cr][j]++; a[cr][i+3]++;a[cr][i+2]++;a[cr][i+1]++;a[cr][i]++; } calc(cr-1); } int main() { T=rdn(); n=rdn(); while(T--) { ans=N; memset(a[0],0,sizeof a[0]); fg=0;//! for(int i=1,u,v;i<=n;i++) { u=rdn(); v=rdn(); if(u)a[0][u<=2?u+11:u-2]++; else fg++; } solve(1); printf("%d ",ans); } return 0; }