考试的时候想了半天,实在是想不到解决的办法,感觉只能暴力。。然后暴力也懒得打了,小数据模拟骗30分hhh
然而正解真的是暴力。。大爆搜。。
然后我的内心拒绝改这道题(TAT)
不过在wcx大佬的帮助下,还是成功的弄过去了。
首先我们明确两个显而易见的问题:答案与花色无关,与出牌顺序无关(废话)
然后我们的切入点是,顺子(连顺等)和带牌(三带一等),因为他们是出牌多的大户。
结论:顺子一定比带牌优(因为可以多出单张)。(不信你可以尝试举出反例)
然后既然这样,我们就先举出全部用带牌的步数,然后一点一点用顺子更新就行了。
有个技巧:按照顺子顺序编号:3,4,5,6···K,A,2。这样的话就可以在循环找顺子的时候方便
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define pos(i,a,b) for(int i=(a);i<=(b);i++) #define N 60 int t,n; int size[N]; int getnum(int x){//小技巧 if(x==1) return 12; if(x==2) return 13; if(x==0) return 14; return x-2; } int ans; int doit(){//找到当前剩余牌下全部带牌的最小步骤 int tmp=0; int tp[10]={0}; pos(i,1,14){ tp[size[i]]++; } while(tp[4]&&tp[2]>=2){//四带二 tp[4]--;tp[2]-=2;tmp++; } while(tp[4]&&tp[1]>=2){//四带一 tp[4]--;tp[1]-=2;tmp++; } while(tp[3]&&tp[2]>=1){//三带二 tp[3]--;tp[2]-=1;tmp++; } while(tp[3]&&tp[1]>=1){//三带一 tp[3]--;tp[1]-=1;tmp++; } tmp+=tp[1]+tp[2]+tp[3]+tp[4];//单牌 return tmp; } void dfs(int cnt){ if(cnt>ans) return; int x=doit(); ans=min(ans,cnt+x); pos(i,1,11){//三连对 int j; for(j=i;size[j]>=3&&j<=12;j++); if(j-i<2) continue; for(int k=j;k-i>=2;k--){ pos(l,i,k-1) size[l]-=3; dfs(cnt+1); pos(l,i,k-1) size[l]+=3; } } pos(i,1,10){//连对 int j; for(j=i;size[j]>=2&&j<=12;j++); if(j-i<3) continue; for(int k=j;k-i>=3;k--){ pos(l,i,k-1) size[l]-=2; dfs(cnt+1); pos(l,i,k-1) size[l]+=2; } } pos(i,1,8){//顺子 int j; for(j=i;size[j]>=1&&j<=12;j++); if(j-i<5) continue; for(int k=j;k-i>=5;k--){ pos(l,i,k-1) size[l]--; dfs(cnt+1); pos(l,i,k-1){ size[l]++; } } } } int main(){ scanf("%d%d",&t,&n); while(t--){ memset(size,0,sizeof(size)); pos(i,1,n){ int x,y; scanf("%d%d",&x,&y); size[getnum(x)]++; } ans=doit(); dfs(0); printf("%d\n",ans); } return 0; }