P2668 [NOIP2015 提高组] 斗地主
我们发现，除了顺子以外，其他的出牌方式和大小无关，我们先爆搜所有的顺子，搜索完之后剩下的牌我们考虑不用顺子，用其他牌型。
此时我们关心的只有单牌、对子、三个、炸弹四种，每种分别最多 \(23,11,7,5\) 个，状态很少，记忆化即可。
注意加强版需要额外一维表示是否有双王，双王可以当对子出，但是不能四带二；但是可以三带一，我们可以特殊判断，如果只剩一张王，把它划入普通单牌的行列。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=1,INF=100,len[]={0,5,3,2};
int T,n,f[24][12][8][6];
int calc(int s[]){
E(i, 4)
if(s[i]<0)return INF;
int sum=0;
E(i, 4)sum+=s[i];
int &v=f[s[1]][s[2]][s[3]][s[4]];
if(~v)return v;
if(!sum)return v=0;
v=INF;
E(i, 4)
Le(k, i, 4){
--s[k],++s[k-i];
v=min(v,calc(s)+1);
if(i==3){
Le(x, 1, 2)
Le(y, x, 4){
--s[y],++s[y-x];
v=min(v,calc(s)+1);
++s[y],--s[y-x];
}
}
if(i==4){
Le(x, 1, 2)
Le(y, x, 4)
Le(z, x, 4){
--s[y],++s[y-x];
--s[z],++s[z-x];
v=min(v,calc(s)+1);
++s[y],--s[y-x];
++s[z],--s[z-x];
}
}
++s[k],--s[k-i];
}
return v;
}
void add(int a[],int l,int r,int k){
Le(i, l, r)
a[i]+=k;
}
bool chk(int a[],int l,int r,int k){
Le(i, l, r)
if(a[i]<k)return false;
return true;
}
int dfs(int cnt[]){
L(i, 14)
if(cnt[i]<0)return INF;
int tmp[5]={};
L(i, 14)
++tmp[cnt[i]];
int ans=calc(tmp);
E(i, 3)
Le(l, 2, 13)
Le(r, l+1, 13){
if(r-l+1<len[i]||!chk(cnt,l,r,i))continue;
add(cnt,l,r,-i);
ans=min(ans,dfs(cnt)+1);
add(cnt,l,r,i);
}
return ans;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T>>n;
memset(f,-1,sizeof f);
W(T){
int cnt[14]{};
E(i, n){
int a,b;
cin>>a>>b;
if(a==1)a=13;
else if(a)a--;
++cnt[a];
}
cout<<dfs(cnt)<<'\n';
}
return 0;
}
加强版
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=1,INF=100,len[]={0,5,3,2};
int T,n,f[24][12][8][6][2];
bool two_king;
int calc(int s[],bool two){
E(i, 4)
if(s[i]<0)return INF;
int sum=0;
E(i, 4)sum+=s[i];
int &v=f[s[1]][s[2]][s[3]][s[4]][two];
if(~v)return v;
if(!sum&&!two)return v=0;
v=INF;
if(two)v=min(v,calc(s,0)+1);
E(i, 4)
Le(k, i, 4){
--s[k],++s[k-i];
v=min(v,calc(s,two)+1);
if(i==3){
Le(x, 1, 2)
Le(y, x, 4){
--s[y],++s[y-x];
v=min(v,calc(s,two)+1);
++s[y],--s[y-x];
}
++s[1];
v=min(v,calc(s,two-1)+1);
--s[1];
}
if(i==4){
Le(x, 1, 2)
Le(y, x, 4)
Le(z, x, 4){
--s[y],++s[y-x];
--s[z],++s[z-x];
v=min(v,calc(s,two)+1);
++s[y],--s[y-x];
++s[z],--s[z-x];
}
}
++s[k],--s[k-i];
}
return v;
}
void add(int a[],int l,int r,int k){
Le(i, l, r)
a[i]+=k;
}
bool chk(int a[],int l,int r,int k){
Le(i, l, r)
if(a[i]<k)return false;
return true;
}
int dfs(int cnt[]){
int tmp[5]={},two=0;
L(i, 14)
if(!i)two=cnt[i]==2;
else ++tmp[cnt[i]];
if(!two)++tmp[cnt[0]];
int ans=calc(tmp,two);
E(i, 3)
Le(l, 2, 13)
Le(r, l+1, 13){
if(r-l+1<len[i]||!chk(cnt,l,r,i))continue;
add(cnt,l,r,-i);
ans=min(ans,dfs(cnt)+1);
add(cnt,l,r,i);
}
return ans;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T>>n;
memset(f,-1,sizeof f);
W(T){
int cnt[14]{};
E(i, n){
int a,b;
cin>>a>>b;
if(a==1)a=13;
else if(a)a--;
++cnt[a];
}
two_king=cnt[0]==2;
cout<<dfs(cnt)<<'\n';
}
return 0;
}