题意
NOIP 2016 斗地主
给你一些牌，按照斗地主的出牌方式，问最少多少次出完所有的牌。
分析
这道题的做法是DFS。
为了体现这道题的锻炼效果，我自己写了好多个代码。
Ver1
直接暴力搞，加深迭代搜索。
发现出牌顺序不影响解决。
优化：先搞顺子，再搞N带N，再搞火箭，再搞N张
int DFS(int nd,int lim)
{
int cur;
int siz;
if (nd>lim)
return 0;
siz=0;
rep(i,3,17)
siz+=cnt[i];
if (nd==lim&&!siz)
return 1;
rep(i,3,17) if (cnt[i]>=4)
{
cnt[i]-=4;
rep(j,3,17) if (cnt[j]>=1)
{
cnt[j]--;
rep(k,3,17) if (cnt[k]>=1)
{
cnt[k]--;
if (DFS(nd+1,lim))
return 1;
cnt[k]++;
}
cnt[j]++;
}
cnt[i]+=4;
}
rep(i,3,14) if (cnt[i]>=3)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=3)
cur++;
rep(j,2,cur-i+1)
{
rep(k,i,i+j-1) cnt[k]-=3;
if (DFS(nd+1,lim))
return 1;
rep(k,i,i+j-1) cnt[k]+=3;
}
}
rep(i,3,14) if (cnt[i]>=2)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=2)
cur++;
rep(j,3,cur-i+1)
{
rep(k,i,i+j-1) cnt[k]-=2;
if (DFS(nd+1,lim))
return 1;
rep(k,i,i+j-1) cnt[k]+=2;
}
}
rep(i,3,14) if (cnt[i]>=1)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=1)
cur++;
rep(j,5,cur-i+1)
{
rep(k,i,i+j-1) cnt[k]--;
if (DFS(nd+1,lim))
return 1;
rep(k,i,i+j-1) cnt[k]++;
}
}
rep(i,3,17) if (cnt[i]>=3)
{
cnt[i]-=3;
rep(j,3,17) if (cnt[j]>=2)
{
cnt[j]-=2;
if (DFS(nd+1,lim))
return 1;
cnt[j]+=2;
}
cnt[i]+=3;
}
rep(i,3,17) if (cnt[i]>=3)
{
cnt[i]-=3;
rep(j,3,17) if (cnt[j]>=1)
{
cnt[j]--;
if (DFS(nd+1,lim))
return 1;
cnt[j]++;
}
cnt[i]+=3;
}
rep(i,3,17) if (cnt[i]>=4)
{
cnt[i]-=4;
if (DFS(nd+1,lim))
return 1;
cnt[i]+=4;
}
rep(i,3,17) if (cnt[i]>=3)
{
cnt[i]-=3;
if (DFS(nd+1,lim))
return 1;
cnt[i]+=3;
}
if (cnt[16]>=1&&cnt[17]>=1)
{
cnt[16]--,cnt[17]--;
if (DFS(nd+1,lim))
return 1;
cnt[16]++,cnt[17]++;
}
rep(i,3,17) if (cnt[i]>=2)
{
cnt[i]-=2;
if (DFS(nd+1,lim))
return 1;
cnt[i]+=2;
}
rep(i,3,17) if (cnt[i]>=1)
{
cnt[i]--;
if (DFS(nd+1,lim))
return 1;
cnt[i]++;
}
return 0;
}Ver2
在Ver1的基础上：
【优化1】
对于顺子的，原本的操作复杂度为15*15*15：
rep(i,3,14) if (cnt[i]>=1)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=1)
cur++;
rep(j,5,cur-i+1)
{
rep(k,i,i+j-1) cnt[k]--;
if (DFS(nd+1,lim))
return 1;
rep(k,i,i+j-1) cnt[k]++;
}
}发现每次的操作都是重复的，所以改成15*15的操作：
rep(i,3,14) if (cnt[i]>=1)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=1)
cur++;
if (cur-i+1>=5)
{
rep(j,i,cur) cnt[j]--;
per(j,cur,i+4)
{
if (j!=cur) cnt[j+1]++;
if (DFS(nd+1,lim))
return 1;
}
rep(j,i,i+4) cnt[j]++;
}
}Ver3
改成深搜+剪枝，加一个dwl属性。
枚举完所有的第一种才能枚举第二种，枚举完所有的第二种才能枚举第三种，etc。
void DFS(int nd,int dwl)
{
int cur;
int siz;
if (nd>=ans)
return;
siz=0;
rep(i,3,17)
siz+=cnt[i];
if (!siz)
{
ans=nd;
return;
}
//①先per优化一个*5
//②改变顺序
if (dwl<=1)
{
if (cnt[16]>=1&&cnt[17]>=1)
{
cnt[16]--,cnt[17]--;
DFS(nd+1,1);
cnt[16]++,cnt[17]++;
}
}
//火箭
if (dwl<=2)
{
rep(i,3,14) if (cnt[i]>=1)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=1)
cur++;
if (cur-i+1>=5)
{
rep(j,i,cur) cnt[j]--;
per(j,cur,i+4)
{
if (j!=cur) cnt[j+1]++;
DFS(nd+1,2);
}
rep(j,i,i+4) cnt[j]++;
}
}
}
//单顺子
if (dwl<=3)
{
rep(i,3,14) if (cnt[i]>=3)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=3)
cur++;
if (cur-i+1>=2)
{
rep(j,i,cur) cnt[j]-=3;
per(j,cur,i+1)
{
if (j!=cur) cnt[j+1]+=3;
DFS(nd+1,3);
}
rep(j,i,i+1) cnt[j]+=3;
}
}
}
//三顺子
if (dwl<=4)
{
rep(i,3,14) if (cnt[i]>=2)
{
cur=i;
while (cur+1<=14&&cnt[cur+1]>=2)
cur++;
if (cur-i+1>=3)
{
rep(j,i,cur) cnt[j]-=2;
per(j,cur,i+2)
{
if (j!=cur) cnt[j+1]+=2;
DFS(nd+1,4);
}
rep(j,i,i+2) cnt[j]+=2;
}
}
}
//双顺子
if (dwl<=5)
{
rep(i,3,17) if (cnt[i]>=4)
{
cnt[i]-=4;
rep(j,3,17) if (cnt[j]>=1)
{
cnt[j]--;
rep(k,j,17) if (cnt[k]>=1)
{
cnt[k]--;
DFS(nd+1,5);
cnt[k]++;
}
cnt[j]++;
}
cnt[i]+=4;
}
}
//四带二
if (dwl<=6)
{
rep(i,3,17) if (cnt[i]>=3)
{
cnt[i]-=3;
rep(j,3,17) if (cnt[j]>=2)
{
cnt[j]-=2;
DFS(nd+1,6);
cnt[j]+=2;
}
cnt[i]+=3;
}
}
//三带二
if (dwl<=7)
{
rep(i,3,17) if (cnt[i]>=3)
{
cnt[i]-=3;
rep(j,3,17) if (cnt[j]>=1)
{
cnt[j]--;
DFS(nd+1,7);
cnt[j]++;
}
cnt[i]+=3;
}
}
//三带一
if (dwl<=8)
{
rep(i,3,17) if (cnt[i]>=4)
{
cnt[i]-=4;
DFS(nd+1,8);
cnt[i]+=4;
}
}
//炸弹
if (dwl<=9)
{
rep(i,3,17) if (cnt[i]>=3)
{
cnt[i]-=3;
DFS(nd+1,9);
cnt[i]+=3;
}
}
//三张牌
if (dwl<=10)
{
rep(i,3,17) if (cnt[i]>=2)
{
cnt[i]-=2;
DFS(nd+1,10);
cnt[i]+=2;
}
}
//对牌
if (dwl<=11)
{
rep(i,3,17) if (cnt[i]>=1)
{
cnt[i]--;
DFS(nd+1,11);
cnt[i]++;
}
}
//单牌
}Ver4
忘记自己干了啥了。。
Ver5
始终是30ptTLE掉。
所以直接看正解了。
http://blog.csdn.net/xieguofu2014/article/details/50193545
既然有正解了，这里就不再写了。
关键在于把操作进行一下分类：顺子、N带N，然后归纳通性。
附网上的STD（含自己乱七八糟的注释）：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
typedef long long ll;
typedef double lf;
const int INF=1<<30;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int T,n,ans;
struct state{
int num[16];
inline int& operator[](int x){return num[x];}
}now;
int temp[10];
void dfs(int);
void group(int c,int s,int depth)
//个数为c，至少要有s个，当前已经进行了depth次
{
for(int st=1,fi;st<=12-s+1;st++){
for(fi=st;now[fi]>=c&&fi<=12;fi++){
now[fi]-=c;
if(fi-st+1>=s)
dfs(depth+1);
}
for(int i=st;i<fi;i++)
now[i]+=c;
}
//暴力剪
}
void dfs(int depth){
if(depth>ans)return;
//剪！！
int sum=0;
for(int i=1;i<=15;i++)
temp[now[i]]++;
//temp[i]: now[j]=i的个数
while(temp[4]>0){
temp[4]--,sum++;
//4张直接出
if(temp[2]>=2)
temp[2]-=2;
else if(temp[1]>=2)
temp[1]-=2;
}
//四带二
while(temp[3]>0){
temp[3]--,sum++;
if(temp[2]>=1)
temp[2]--;
else if(temp[1]>=1)
temp[1]--;
}
//三带
sum+=temp[1]+temp[2];
//一和二直接
if(temp[1]>=2&&now[14]>=1&&now[15]>=1)
sum--;
//处理JOKER的情况：sum--
temp[1]=temp[2]=0;
if(depth+sum<ans)
ans=depth+sum;
//若depth+sum<ans那么就更新
//上面一大段，解决的是：昨晚所有的顺子之后，直接贪心求解的情况
group(1,5,depth);
//枚举单张，长度为5的单顺子
group(2,3,depth);
//枚举双张，长度为3的双顺子
group(3,2,depth);
//枚举3张，长度为2的三顺子
}
void work(){
memset(now.num,0,sizeof now.num);
ans=1<<30;
for(int i=1;i<=n;i++){
int k=read(),c=read();
if(k==0)
now[13+c]++;
else if(k<=2)
now[11+k]++;
else
now[k-2]++;
}
dfs(0);
printf("%d\n",ans);
}
int main(){
freopen("a.in","r",stdin);
freopen("a.ans","w",stdout);
T=read(),n=read();
for(int turn=1;turn<=T;turn++)
work();
return 0;
}附自己的AC代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
const int MAX=INT_MAX;
int cas;
int n;
int cnt[16];
int ans;
int cal[5];
inline int rd(void)
{
int x=0,f=1; char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int Calc(void)
{
int sum=0;
memset(cal,0,sizeof cal);
rep(i,1,15)
cal[cnt[i]]++;
while (cal[4]>0)
{
sum++; cal[4]--;
if (cal[2]>=2)
cal[2]-=2;
else if (cal[1]>=2)
cal[1]-=2;
}
while (cal[3]>0)
{
sum++; cal[3]--;
if (cal[2]>=1)
cal[2]--;
else if (cal[1]>=1)
cal[1]--;
}
sum+=(cal[2]+cal[1]);
if (cal[1]>=2&&cnt[14]>=1&&cnt[15]>=1)
sum--;
return sum;
}
void DFS(int);
void Solve(int c,int len,int dep)
{
int cur;
rep(i,1,12-len+1) if (cnt[i]>=c)
{
cur=i;
while (cur+1<=12&&cnt[cur+1]>=c)
cur++;
if (cur-i+1>=len)
{
rep(j,i,cur) cnt[j]-=c;
per(j,cur,i+len-1)
{
if (j!=cur) cnt[j+1]+=c;
DFS(dep+1);
}
rep(j,i,i+len-1) cnt[j]+=c;
}
}
}
void DFS(int dep)
{
if (dep>ans)
return;
int sum=Calc();
ans=min(ans,sum+dep);
Solve(1,5,dep);
Solve(2,3,dep);
Solve(3,2,dep);
}
int main(void)
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
cas=rd(),n=rd();
rep(tur,1,cas)
{
int x,y; memset(cnt,0,sizeof cnt);
rep(i,1,n)
{
x=rd(),y=rd();
if (0<x&&x<=2) cnt[x+11]++;
else if (x>2) cnt[x-2]++;
else cnt[y+13]++;
}
ans=MAX;
DFS(0);
printf("%d\n",ans);
}
return 0;
}小结
（1）对于操作很多很繁杂的问题时，分类的作用必不可少。
分类的目的在于：限定具有相同结构的一些对象，研究它们的通性，更好地优化问题。
本题就是按照顺子、N带N这两个来分类，先处理完所有的顺子，N带N的就可以贪心了。
其实这种东西在化学课上才刚讲完，为什么想不出来，真的应该好好反思一下。
（2）当操作顺序不影响的时候，我们的想法是定序：规定枚举顺序。即：必然从前面枚举到后面，减少一个数量级。
其实最后的代码并没有使用定序的优化，但是优化后效果更佳。