首页 > 代码库 > 【uoj147】NOIP2015—斗地主
【uoj147】NOIP2015—斗地主
http://uoj.ac/problem/147 (题目链接)
题意
打牌。。。
Solution
其实很简单的搜索，当年还是太年轻了。稍微想一想，顺子肯定是要先打掉的，因为顺子所包含的牌最多，所以我们可以以打出了多少张顺子为状态进行搜索，每一种状态，贪心去计算一下对于当前状态还需要打多少次才能将牌打完，不断更新答案即可。
代码：
// uoj147#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>#define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;const int maxn=30;int c[5],a[maxn],n,T,ans;int cal() { memset(c,0,sizeof(c)); for (int i=0;i<=13;i++) c[a[i]]++; int tot=0; while (c[4] && c[2]>1) c[4]--,c[2]-=2,tot++; while (c[4] && c[1]>1) c[4]--,c[1]-=2,tot++; while (c[4] && c[2]) c[4]--,c[2]--,tot++; while (c[3] && c[2]) c[3]--,c[2]--,tot++; while (c[3] && c[1]) c[3]--,c[1]--,tot++; return tot+c[1]+c[2]+c[3]+c[4];}void dfs(int x) { if (x>=ans) return; int tmp=cal(); ans=min(ans,tmp+x); for (int i=2;i<=13;i++) { int j=i; while (a[j]>=3) j++; if (j-i>=2) { for (int k=i+1;k<=j-1;k++) { for (int l=i;l<=k;l++) a[l]-=3; dfs(x+1); for (int l=i;l<=k;l++) a[l]+=3; } } } for (int i=2;i<=13;i++) { int j=i; while (a[j]>=2) j++; if (j-i>=3) { for (int k=i+2;k<=j-1;k++) { for (int l=i;l<=k;l++) a[l]-=2; dfs(x+1); for (int l=i;l<=k;l++) a[l]+=2; } } } for (int i=2;i<=13;i++) { int j=i; while (a[j]>=1) j++; if (j-i>=5) { for (int k=i+4;k<=j-1;k++) { for (int l=i;l<=k;l++) a[l]--; dfs(x+1); for (int l=i;l<=k;l++) a[l]++; } } }}int main() { int T;scanf("%d%d",&T,&n); while (T--) { memset(a,0,sizeof(a)); for (int x,y,i=1;i<=n;i++) { scanf("%d%d",&x,&y); if (x==1) x=13; else if (x) x--; a[x]++; } ans=n; dfs(0); printf("%d\n",ans); } return 0;}
【uoj147】NOIP2015—斗地主
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。