【NOIp 2015】【DFS】斗地主

题面

自己网上去搜吧…

代码

#include <cstdio> #include <cstring> #include <algorithm> #define INF 10000000 #define maxn 40 using namespace std; int t,n,temp,a,zhang[maxn],ans=INF; void dfs(int,int,int,int); void shunzi(int,int,int,int,int); void chu(int x,int dep,int left){//在第dep手牌的时候出x号牌，还剩left张牌 if(x>14) return; if(dep>ans) return;//如果比当前最优解差就跳出 if(left==0){ ans=min(ans,dep); return; }//如果剩下的手牌为0，记录答案 if(zhang[x]==0) chu(x+1,dep,left);//如果x号牌出完了就该出x+1号牌 else for(int i=zhang[x];i>0;i--) dfs(x,i,dep,left);//搜索第x号牌出1~出完的情况 return; } void dfs(int p,int shu,int dep,int left){//第p张牌出shu张，出了dep手牌，剩下left张牌 if(shu==4){ zhang[p]-=4; chu(p,dep+1,left-4);//出炸弹 //出四带二（四带一对，四带两对，四带两张） for(int i=p+1;i<=14;i++){ if(zhang[i]>=1){ zhang[i]--; for(int j=p+1;j<=14;j++){ if(zhang[j]>=1){ zhang[j]--; chu(p,dep+1,left-6); zhang[j]++; } } zhang[i]++; } }//四带两张或一对 for(int i=p+1;i<=14;i++){ for(int j=i+1;j<=14;j++){ if(zhang[i]>=2&&zhang[j]>=2){ zhang[i]-=2; zhang[j]-=2; chu(p,dep+1,left-8); zhang[i]+=2; zhang[j]+=2; } } } //四带两对 zhang[p]+=4; return; }else if(shu==3){ zhang[p]-=3; //出三顺子 if(p>2){ for(int i=p+1;i<=14;i++){ if(zhang[i]<3) break; else shunzi(p,i,3,dep,left); } } //出三带二 for(int i=p+1;i<=14;i++){ if(zhang[i]>=2){ zhang[i]-=2; chu(p,dep+1,left-5); zhang[i]+=2; } } //出三带一 for(int i=p+1;i<=14;i++){ if(zhang[i]>=1){ zhang[i]-=1; chu(p,dep+1,left-4); zhang[i]+=1; } } chu(p,dep+1,left-3); zhang[p]+=3; return; }else if(shu==2){ zhang[p]-=2; //出双顺子 if(p>2&&zhang[p+1]>=2&&zhang[p+2]>=2) for(int i=p+2;i<=14;i++){ if(zhang[i]<2){ break; } else shunzi(p,i,2,dep,left); } //出四带两对 for(int i=p+1;i<=14;i++){ if(zhang[i]>=4){ zhang[i]-=4; chu(p,dep+1,left-6); //四带一对 for(int j=p+1;j<=14;j++){ if(zhang[j]>=2){ zhang[j]-=2; chu(p,p+1,left-8); zhang[j]+=2; } } zhang[i]+=4; } } //出三带二 for(int i=p+1;i<=14;i++){ if(zhang[i]>=3){ zhang[i]-=3; chu(p,dep+1,left-5); zhang[i]+=3; } } //出单对 chu(p,dep+1,left-2); zhang[p]+=2; return; }else if(shu==1){ zhang[p]-=1; //出顺子 if(p>2&&p<11&&zhang[p+1]>=1&&zhang[p+2]>=1&&zhang[p+3]>=1&&zhang[p+4]>=1){//因为大小王不能进顺子所以p<11 for(int i=p+4;i<=14;i++){ if(zhang[i]<1){ break; } else shunzi(p,i,1,dep,left); } } //出四带两张单牌 for(int i=p+1;i<=14;i++){ if(zhang[i]>=4){ zhang[i]-=4; for(int j=p+1;j<=14;j++){ if(zhang[j]>=1){ zhang[j]-=1; chu(p,dep+1,left-6); zhang[j]+=1; } } zhang[i]+=4; } } //出三带一 for(int i=p+1;i<=14;i++){ if(zhang[i]>=3){ zhang[i]-=3; chu(p,dep+1,left-4); zhang[i]+=3; } } //出单张 chu(p,dep+1,left-1); zhang[p]+=1; return; } return; } void shunzi(int x,int y,int type,int dep,int left){//从第x到y张牌开始出顺子，出type种顺子 for(int i=x+1;i<=y;i++) zhang[i]-=type; chu(x,dep+1,left-type*(y-x+1)); for(int i=x+1;i<=y;i++) zhang[i]+=type; return; } int main(){ freopen("landlords.in","r",stdin); freopen("landlords.out","w",stdout); scanf("%d%d",&t,&n); while(t--){ memset(zhang,0,sizeof(zhang)); ans=INF; for(int i=1;i<=n;i++) { scanf("%d%d",&a,&temp); if(a==1) zhang[14]++; else zhang[a]++; } chu(0,0,n); printf("%d\n",ans); } return 0; } //hcy太强辣~\(≧▽≦)/~啦啦啦

转载于:https://www.cnblogs.com/leotan0321/p/6081376.html