首页 > ACM题库 > HDU-杭电 > hdu 2775 Videopoker[解题报告]C++
2014
02-14

hdu 2775 Videopoker[解题报告]C++

Videopoker

问题描述 :

Videopoker is the slot machine variant of the currently immensely popular game of poker. It is a variant on draw poker. In this game the player gets a hand consisting of five cards randomly drawn from a standard 52-card deck. From this hand, the player may discard any number of cards (between 0 and 5, inclusive), and change them for new cards randomly drawn from the remainder of the deck. After that, the hand is evaluated and the player is rewarded according to a payout structure. A common payout structure is as follows:

Once you know the payout structure, you can determine for a given hand which cards you must change to maximize your expected reward. We’d like to know this expected reward, given a hand.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:* One line with nine integers xi (0 ≤ xi ≤ 1000$) describing the payout structure. The numbers are in increasing order and describe the payout for one pair, two pair, etc, until the royal flush.
* One line with one integer n (1 ≤ n ≤ 10): the number of starting hands to follow.
* n lines, each describing a starting hand. A hand consists of five space separated tokens of the form Xs, with X being the rank (`2′…`9′, `T’, `J’, `Q’, `K’ or `A’) and s being the suit (`c’, `d’, `h’ or `s’).

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:* One line with nine integers xi (0 ≤ xi ≤ 1000$) describing the payout structure. The numbers are in increasing order and describe the payout for one pair, two pair, etc, until the royal flush.
* One line with one integer n (1 ≤ n ≤ 10): the number of starting hands to follow.
* n lines, each describing a starting hand. A hand consists of five space separated tokens of the form Xs, with X being the rank (`2′…`9′, `T’, `J’, `Q’, `K’ or `A’) and s being the suit (`c’, `d’, `h’ or `s’).

样例输入:

1
1 2 3 4 5 10 25 100 250
5
Ah Ac Ad As 2s
Ks Qs Js Ts 2h
Ks Qs 2d 2h 3s
2d 4h 5d 3c 9c
2h 3h 6d 8h Tc

样例输出:

25.000000
8.9574468
1.5467160
0.9361702
0.6608135


AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int v[10],n,a[8][2],rest[20],now[8],occ[23],tot[100];
long long score[100];
char s[21];
int getrank(char ch){
	if(ch=='A')return 1;
	if(ch=='T')return 10;
	if(ch=='J')return 11;
	if(ch=='Q')return 12;
	if(ch=='K')return 13;
	return ch-'2'+2;
}
int getsuit(char ch){
	if(ch=='c')return 1;
	if(ch=='d')return 2;
	if(ch=='h')return 3;
	if(ch=='s')return 4;
}
bool can(int col,int mask)
{
	for(int i=0;i<5;++i)
		for(int j=i+1;j<5;++j)
			if(now[i]==now[j])
				return false;
	for(int i=0;i<5;++i)
		if((mask&(1<<i))==0)
		{
			if(a[i][1]!=col)return false;
		}
		else
		{
			for(int j=0;j<5;++j)
				if(a[j][0]==now[i]&&a[j][1]==col)
					return false;
		}
	return true;
}
bool is0()
{
	for(int i=1;i<=14;++i)
		if(occ[i]==2)
			return 1;
	return 0;
}
bool is1()
{
	int ret=0;
	for(int i=1;i<=14;++i)
		if(occ[i]==2)
			++ret;
	return ret==2;
}
bool is2()
{
	for(int i=1;i<=14;++i)
		if(occ[i]==3)
			return 1;
	return 0;
}
bool is3()
{
	if(occ[1]&&occ[10]&&occ[11]&&occ[12]&&occ[13])
		return true;
	for(int i=1;i+5-1<=13;++i)
		if(occ[i]&&occ[i+1]&&occ[i+2]&&occ[i+3]&&occ[i+4])
			return true;
	return false;
}
bool is5()
{
	for(int i=1;i<=14;++i)
		if (occ[i] == 3)
			for(int j=1;j<=14;++j)
				if(occ[j]==2)
					return true;
	return false;
}
bool is6()
{
	for(int i=1;i<=14;++i)
		if(occ[i]==4)
			return 1;
	return 0;
}
int getscore()
{
	if(is6())return v[6];
	if(is5())return v[5];
	if(is3())return v[3];
	if(is2())return v[2];
	if(is1())return v[1];
	if(is0())return v[0];
	return 0;
}
int getsame(int *r)
{
	if(occ[1]&&occ[10]&&occ[11]&&occ[12]&&occ[13])
		return 8;
	for(int i=1;i+5-1<=13;++i)
		if(occ[i]&&occ[i+1]&&occ[i+2]&&occ[i+3]&&occ[i+4])
			return 7;
	return 4;
}
void search(int u,int cnt, int mask)
{
	if(u==5)
	{
		memset(occ,0,sizeof(occ));
		for(int i=0;i<5;++i)
			++occ[now[i]];
		tot[mask] += cnt;
		int tmp = 0;
		for(int i=1;i<=4;++i)
			if(can(i,mask)) {
				++ tmp;
			}
		if (is6() || is5()) tmp = 0;
		if (tmp) score[mask] += (long long)tmp * (long long)v[getsame(now)];
		score[mask]+=(long long)(cnt - tmp)*(long long)getscore();
		return;
	}
	now[u]=a[u][0];
	search(u + 1, cnt , mask);
	for(int i=1;i<=13;++i)
		if(rest[i])
		{
			--rest[i];
			now[u]=i;
			search(u+1,cnt*(rest[i]+1),mask|(1<<u));
			++rest[i];
		}
}
int main()
{
	int _;
	for(scanf("%d",&_);_--;)
	{
		for(int i=0;i<9;++i)scanf("%d",v+i);
		scanf("%d%*c",&n);
		for (int k = 0; k < n; ++ k) {
			for(int i=1;i<=13;++i)rest[i]=4;
			for(int i=0;i<5;++i)
			{
				scanf("%s",s);
				a[i][0]=getrank(s[0]);
				--rest[a[i][0]];
				a[i][1]=getsuit(s[1]);
			}
			memset(tot, 0, sizeof(tot));
			memset(score, 0, sizeof(score));
			search(0,1,0);
			double ans = 0.;
			//cout << tot[0] << ' ' << score[0] << endl;
			for (int  i = 0; i < (1<<5); ++ i)
				if (tot[i]) {
					//cout << score[i] << ' ' << tot[i] << ' ' << i << endl;
					ans = max(ans, (double)score[i] / (double)tot[i]);
				}
			printf("%.8f\n",ans);
		}
	}
	return 0;
}

 


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。