三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> P2668 斗地主 -> 正文阅读
 

[C++]P2668 斗地主

P2668 斗地主 题目描述
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如下:

输入输出格式 输入格式:
第一行包含用空格隔开的2个正整数T和n,表示手牌的组数以及每组手牌的张数。
接下来T组数据,每组数据n行,每行一个非负整数对aibi表示一张牌,其中ai示牌的数码,bi表示牌的花色,中间用空格隔开。特别的,我们用1来表示数码A,11表示数码J,12表示数码Q,13表示数码K;黑桃、红心、梅花、方片分别用1-4来表示;小王的表示方法为01,大王的表示方法为02。
输出格式:
共T行,每行一个整数,表示打光第i手牌的最少次数。
输入输出样例
输入样例#1:

1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

输出样例#1:

3

输入样例#2:

1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2

输出样例#2:

6

说明
样例1说明
共有1组手牌,包含8张牌:方片7,方片8,黑桃9,方片10,黑桃J,黑桃5,方片A以及黑桃A。可以通过打单顺子(方片7,方片8,黑桃9,方片10,黑桃J),单张牌(黑桃5)以及对子牌(黑桃A以及方片A)在3次内打光。
对于不同的测试点, 我们约定手牌组数T与张数n的规模如下:

数据保证:所有的手牌都是随机生成的。
尼玛广搜323行85分,深搜压行之后57行就A了,,,‘

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=23;
 7 int read(int & n)
 8 {
 9     char c='-';int x=0;
10     while(c<'0'||c>'9')c=getchar();
11     while(c>='0'&&c<='9')
12     {
13         x=x*10+(c-48);
14         c=getchar();
15     }
16     n=x;
17 }
18 int T,n,p,hs;
19 int ans;
20 int card_num[MAXN];// 记录每一种数码的出现次数
21 int happen[MAXN];// 记录数量的出现次数 
22 /*比如说3出现了两次,A出现了两次,那么happen[2]==2*/ 
23 int take_num[5]={0,5,3,2};// 斗地主的规则,分别对应单顺双顺三顺 
24 void dfs(int now)// now是指已经操作的次数 
25 {
26     if(now>ans)
27         return ;// 剪枝 
28     memset(happen,0,sizeof(happen));
29     for(int i=0;i<=14;i++)
30         happen[card_num[i]]++;
31     int cs=0;// 本轮的操作次数 
32     while(happen[4])// 四带 
33     {
34         cs++;
35         happen[4]--;
36         if(happen[2]>=2)//根据贪心的原理,能出两张则不出一张 
37            happen[2]-=2;// 能带两对对牌不带一对对牌 
38         else if(happen[1]>=2)
39             happen[1]-=2;//四张牌每次可以带两张单牌 
40     }
41     while(happen[3])
42     {
43         cs++;
44         happen[3]--; 
45         if  (happen[2])
46             happen[2]--;
47         else if(happen[1])
48             happen[1]--;//思路同上,三张牌进行带牌的时候只能带一张 
49     }
50     if(card_num[0]&&card_num[1]&&happen[1]>=2)
51         cs--;//当大王和小王可以同时出的时候就当做对牌一起出
52     // 因为在后面一条语句中需要+happen[1],所以默认是大王小王当单牌出
53     // 那么同时有大王小王就需要两次操作,实际上一次操作就可以完成,相当于2-1=1 
54     cs=cs+happen[1]+happen[2];
55     // 剩下的对牌和单牌需要每组一次操作 
56     ans=min(ans,cs+now);// 更新答案 
57     for(int k=1;k<=3;k++)// k代表顺子的类型,1:单顺 2:双顺 3:三顺 
58     {
59         for(int i=3,j;i<=14;++i)// 枚举每一张牌,因为2不能在顺子中出现,所以无视 
60         {
61             for(j=i;card_num[j]>=k&&j<=14;++j)
62             {//在可行的情况和区间内寻找顺子 
63                 card_num[j]-=k;// 先减去,后面会加回来 
64                 if(j-i+1>=take_num[k])// 可以当顺子出 
65                     dfs(now+1);// 就当顺子出 
66             }
67             while(j>i)// 递归的回溯 
68                 card_num[--j]+=k; 
69         }
70     }
71     
72 }
73 int main()
74 {
75     read(T);read(n);
76     while(T--)
77     {
78         memset(card_num,0,sizeof(card_num));
79         ans=n;
80         for(int i=1;i<=n;i++)
81         {
82             read(p);read(hs);
83             if(p==0)card_num[hs-1]++;
84             // 把小王看做0,大王看做1.保证card_num数组没有冲突 
85             else if(p==1)card_num[14]++;// 把A看做14 
86             else card_num[p]++;
87         }
88         
89         dfs(0);
90         printf("%d\n",ans); 
91     }
92     return 0;
93 }

  C++ 最新文章
QT5简介
洛谷P3954 成绩【民间数据】
POJ 3292 Semi
Dev
使用一位数组解决 1 1 2 3 5 8 13 数列问题
Spring框架xml配置文件 复杂类型属性注入—
随手小代码——生成GUID
斐波拉契数列
EC笔记:第4部分:21、必须返回对象时,别返
STL六大组件之——容器知识大扫盲
上一篇文章      下一篇文章      查看所有文章
加:2017-06-17 01:43:20  更:2017-06-17 01:43:26 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年11日历
2017-11-20 5:48:26
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库