[NOIp 2015]斗地主

Description

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

[NOIp 2015]斗地主

Input

第一行包含用空格隔开的2个正整数T,N,表示手牌的组数以及每组手牌的张数。

接下来T组数据,每组数据N行,每行一个非负整数对Ai,Bi,表示一张牌,其中Ai表示牌的数码,Bi表示牌的花色,中间用空格隔开。特别的,我们用1来表示数码A,11表示数码J,12表示数码Q,13表示数码K;黑桃、红心、梅花、方片分别用1-4来表示;小王的表示方法为01,大王的表示方法为02。

Output

共T行,每行一个整数,表示打光第T组手牌的最少次数。

Sample Input

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

Sample Output

3

HINT

共有1组手牌,包含8张牌:方片7,方片8,黑桃9,方片10,黑桃J,黑桃5,方

片A以及黑桃A。可以通过打单顺子(方片7,方片8,黑桃9,方片10,黑桃J),单张
牌(黑桃5)以及对子牌(黑桃A以及方片A)在3次内打光。
T<=10
N<=23

题解

抓取有用信息:

出牌顺序不影响出牌次数。

30分算法:

1、$T≤100$,$n≤4$;
2、先特判掉三带一的情况,然后有几种不同点数的牌,答案就是几;注意两张王可以看成是相同点数;
3、时间复杂度$O(T*n)$

100分算法:

1、$T≤10$,$n≤23$;
2、既然出牌顺序不影响,那么不妨先出对子,包括单顺、双顺、三顺。具体就是直接暴力枚举每一个顺子,然后出掉,再枚举顺子,再出掉......
3、这样可以过吗?
一个顺子至少有$5$张牌,最多出$4$组顺子,递归层数很小;
然后在一组牌内可以产生$O(K^2)$个顺子,其中$K$表示能成为顺子组成部分的牌的种数,在这里$K=12$,然后这里的复杂度就是$O(K^8)$,看起来很大,其实实测完全可以跑出来;
4、然后就可以不考虑顺子了,那么对于剩下的牌,我们就只能一个一个或者一对一对或者一带一带地出,也就是说出牌次数与牌的点数无关了;
5、那么我们可以预处理一个$dp[a][b][c][d]$,表示手牌有"$d$张单牌,$c$个对子,$b$个三张,$a$个炸弹"的时候,把牌出完的最少次数。
6、可以动态规划求解,$joker$可以拿出单独讨论。
7、时间复杂度$O(n^4+T*K^8)$。

这道题还有数据增强版,就是多考虑几个条件,把牌拆开(详见代码中的$extra$)。

 #include <set>
#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int INF = ~0u>>;
const int lenth[] = {, , , }; int n, t;
int card[], f[][][][];
int ans; int getrest(int r1, int r2, int r3, int r4, int joker){
if (joker == ) r1++,joker--;
if (joker) return Min(f[r4][r3][r2][r1+], f[r4][r3][r2][r1]+);
return f[r4][r3][r2][r1];
}
void dfs(int t){
if (t >= ans) return;
int c[] = {};
for (int i = ; i <= ; i++) c[card[i]]++;
ans = Min(ans, t+getrest(c[], c[], c[], c[], card[]));
for (int len = ; len <= ; len++)
  for (int i = ; i <= ; i++){
  int j = i;
  for (;j <= && card[j] >= len; j++){
     card[j] -= len;
    if (j-i+ >= lenth[len]) dfs(t+);
  }
  for (j--; j >= i; j--) card[j] += len;
  }
}
void pre(){
memset(f, /, sizeof(f));
f[][][][] = ;
for (int i = ; i <= n; i++)
  for (int j = ; j <= n; j++)
   for (int p = ; p <= n; p++)
     for (int q = ; q <= n; q++)
      if (i*+j*+p*+q <= n)
     {
       f[i][j][p][q] = i+j+p+q;
       if (i){
       if (p >= ) f[i][j][p][q] = Min(f[i][j][p][q], f[i-][j][p-][q]+);//四带两对
       if (q >= ) f[i][j][p][q] = Min(f[i][j][p][q], f[i-][j][p][q-]+);//四带二
       if (p) f[i][j][p][q] = Min(f[i][j][p][q], f[i][j][p-][q+]);//extra:把对子拆成一个单的
       f[i][j][p][q] = Min(f[i][j][p][q], f[i-][j][p+][q]);//extra:把炸拆成两对
       f[i][j][p][q] = Min(f[i][j][p][q], f[i-][j+][p][q+]);//extra:把炸拆成单张和三张
       f[i][j][p][q] = Min(f[i][j][p][q], f[i-][j][p][q]+);//出炸
       }
       if (j){
       if (p) f[i][j][p][q] = Min(f[i][j][p][q], f[i][j-][p-][q]+);//三带一对
       if (q) f[i][j][p][q] = Min(f[i][j][p][q], f[i][j-][p][q-]+);//三带一
       f[i][j][p][q] = Min(f[i][j][p][q], f[i][j-][p+][q+]);//extra:三拆成二+一
       f[i][j][p][q] = Min(f[i][j][p][q], f[i][j-][p][q]+);//直接出三张
       }
       if (p) f[i][j][p][q] = Min(f[i][j][p][q], f[i][j][p-][q]+);//直接出对子
      if (q) f[i][j][p][q] = Min(f[i][j][p][q], f[i][j][p][q-]+);//直接出单张
     }
} int main(){
scanf("%d%d", &t, &n);
pre();
while (t--){
   memset(card, , sizeof(card));
   int a, b;
  ans = n;
  for (int i = ; i <= n; i++){
   scanf("%d%d", &a, &b);
   if (a == ) card[]++;
   else card[a]++;
   }
   dfs();
   printf("%d\n", ans);
}
return ;
}
上一篇:advanced installer详细使用教程


下一篇:安卓整蛊游戏 源码