【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太強辣~\(≧▽≦)/~啦啦啦