[THOJ 1599] dices 期望DP

题意

  有 5 个骰子, 14 个盒子.

  玩 14 轮游戏, 每次投骰子, 你将骰子放入同一个之前没有放入的盒子中.

  最大化在最优策略下玩家的分数.

  玩家的分数这样计算:

    设扔入的盒子的标号为 i .

    当 1 <= i <= 6 时, 分数为 i 的个数 * i .

    当 i = 7 时, 若有两对骰子相同, 分数为点数之和.

    当 i = 8 时, 若至少有 3 个相同, 分数为点数之和.

    当 i = 9 时, 若至少有 4 个相同, 分数为点数之和.

    当 i = 10 时, 若 3 个相同, 另外两个也先相同, 分数为 25 .

    当 i = 11 时, 若有连续 4 个, 分数为 30 .

    当 i = 12 时, 若有连续 5 个, 分数为 40 .

    当 i = 13 时, 若骰子分数都相同, 分数为 50 .

    当 i = 14 时, 分数为点数之和.

分析

  状压DP, f[x] 表示状态为 x , 到完结的最大期望分数.

  f[x] = ∑ P(S) max(f[S + {i}] + w[S][i]) .

  预处理每种状态放入每个盒子的分数 w[S][i] , 以及这种状态出现的概率 P[S] .

实现

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cctype>
  5 #include <map>
  6 using namespace std;
  7 #define F(i, a, b) for (register int i = (a); i <= (b); i++)
  8 #define D(i, a, b) for (register int i = (a); i >= (b); i--)
  9 #define db double
 10
 11 db p[10];
 12
 13 int cnt[10];
 14 int idx, id[500], pos[50000];
 15 db P[500], w[500][15];
 16
 17 void Prework(int dep, db Ps) {
 18     if (dep > 5) {
 19         int St = 0; F(i, 1, 6) St = St * 6 + cnt[i];
 20
 21         bool tag = (pos[St] > 0);
 22         if (!tag) id[++idx] = St, pos[St] = idx;
 23
 24         int Loc = pos[St];
 25         P[Loc] += Ps;
 26
 27         if (!tag) {
 28             int sum = 0; F(i, 1, 6) sum += i * cnt[i];
 29
 30             w[Loc][14] = sum;
 31
 32             bool Same = false;
 33             F(i, 1, 6) if (cnt[i] == 5) Same = true;
 34             if (Same) w[Loc][13] = 50;
 35
 36             bool Five = (cnt[2] > 0 && cnt[3] > 0 && cnt[4] > 0 && cnt[5] > 0);
 37             if (Five && (cnt[1] > 0 || cnt[6] > 0))
 38                 w[Loc][12] = 40;
 39
 40             bool Four = (cnt[1] > 0 && cnt[2] > 0 && cnt[3] > 0 && cnt[4] > 0);
 41             Four |= (cnt[2] > 0 && cnt[3] > 0 && cnt[4] > 0 && cnt[5] > 0);
 42             Four |= (cnt[3] > 0 && cnt[4] > 0 && cnt[5] > 0 && cnt[6] > 0);
 43             if (Four) w[Loc][11] = 30;
 44
 45             bool Three = false, Two = false;
 46             F(i, 1, 6) {
 47                 if (cnt[i] == 3) Three = true;
 48                 if (cnt[i] == 2) Two = true;
 49             }
 50             if (Three && Two) w[Loc][10] = 25;
 51
 52             Four = false;
 53             F(i, 1, 6) if (cnt[i] >= 4) Four = true;
 54             if (Four) w[Loc][9] = sum;
 55
 56             Three = false;
 57             F(i, 1, 6) if (cnt[i] >= 3) Three = true;
 58             if (Three) w[Loc][8] = sum;
 59
 60             int twocnt = 0;
 61             F(i, 1, 6) twocnt += (cnt[i] >= 2);
 62             if (twocnt >= 2) w[Loc][7] = sum;
 63
 64             F(i, 1, 6) w[Loc][i] = i * cnt[i];
 65         }
 66
 67         return;
 68     }
 69     F(w, 1, 6) {
 70         cnt[w]++;
 71         Prework(dep+1, Ps * p[w]);
 72         cnt[w]--;
 73     }
 74 }
 75
 76 db f[20000];
 77
 78 int main(void) {
 79     #ifndef ONLINE_JUDGE
 80         freopen("dices.in", "r", stdin);
 81     #endif
 82
 83     int nT; scanf("%d", &nT);
 84     F(cas, 1, nT) {
 85         F(i, 1, 6) scanf("%lf", p+i);
 86
 87         idx = 0, memset(id, 0, sizeof id), memset(pos, 0, sizeof pos);
 88         memset(P, 0, sizeof P), memset(w, 0, sizeof w);
 89         Prework(1, 1);
 90
 91         memset(f, 0, sizeof f);
 92         D(St, (1 << 14) - 2, 0)
 93             F(Loc, 1, idx) {
 94                 db Max = 0;
 95                 F(Dec, 1, 14) if (~St >> Dec-1 & 1)
 96                     Max = max(Max, w[Loc][Dec] + f[St | (1 << Dec-1)]);
 97                 f[St] += P[Loc] * Max;
 98             }
 99         printf("Case #%d: %0.6lf\n", cas, f[0]);
100     }
101
102     return 0;
103 }
时间: 09-15

[THOJ 1599] dices 期望DP的相关文章

【bzoj4872】[Shoi2017]分手是祝愿 数论+期望dp

题目描述 Zeit und Raum trennen dich und mich. 时空将你我分开. B 君在玩一个游戏,这个游戏由 n 个灯和 n 个开关组成,给定这 n 个灯的初始状态,下标为从 1 到 n 的正整数.每个灯有两个状态亮和灭,我们用 1 来表示这个灯是亮的,用 0 表示这个灯是灭的,游戏的目标是使所有灯都灭掉.但是当操作第 i 个开关时,所有编号为 i 的约数(包括 1 和 i)的灯的状态都会被改变,即从亮变成灭,或者是从灭变成亮.B 君发现这个游戏很难,于是想到了这样的一个

HDOJ 1145 So you want to be a 2n-aire? 期望DP

期望DP So you want to be a 2n-aire? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 267    Accepted Submission(s): 197 Problem Description The player starts with a prize of $1, and is asked a seq

HDU 4336 Card Collector (期望DP+状态压缩 或者 状态压缩+容斥)

题意:有N(1<=N<=20)张卡片,每包中含有这些卡片的概率,每包至多一张卡片,可能没有卡片.求需要买多少包才能拿到所以的N张卡片,求次数的期望. 析:期望DP,是很容易看出来的,然后由于得到每张卡片的状态不知道,所以用状态压缩,dp[i] 表示这个状态时,要全部收齐卡片的期望. 由于有可能是什么也没有,所以我们要特殊判断一下.然后就和剩下的就简单了. 另一个方法就是状态压缩+容斥,同样每个状态表示收集的状态,由于每张卡都是独立,所以,每个卡片的期望就是1.0/p,然后要做的就是要去重,既然

Topcoder SRM656div1 250 ( 期望DP )

Problem Statement    Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].Charlie chooses the pancakes he is going to serve using t

期望dp 知识点

求期望dp有两种类型 1.概率dp 2.高斯消元 相关知识点可以看这里  一篇很好的文章  http://kicd.blog.163.com/blog/static/126961911200910168335852/ http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html 高斯消元  http://wenku.baidu.com/link?url=Q8ES7wreJk3et-VrHtp6CVNuyqX18YdB3c841-o

string (KMP+期望DP)

Time Limit: 1000 ms   Memory Limit: 256 MB Description  给定一个由且仅由字符 'H' , 'T' 构成的字符串$S$. 给定一个最初为空的字符串$T$ , 每次随机地在$T$的末尾添加 'H' 或者 'T' . 问当$S$为$T$的后缀时, 在末尾添加字符的期望次数. Input 输入只有一行, 一个字符串$S$. Output 输出只有一行, 一个数表示答案. 为了防止运算越界, 你只用将答案对$10^9+7$取模. Sample Inp

【期望DP】

[总览] [期望dp] 求解达到某一目标的期望花费:因为最终的花费无从知晓(不可能从$\infty$推起),所以期望dp需要倒序求解. 设$f[i][j]$表示在$(i, j)$这个状态实现目标的期望值(相当于是差距是多少). 首先$f[n][m] = 0$,在目标状态期望值为0.然后$f = (\sum f' × p) + w $,$f'$为上一状态(距离目标更近的那个,倒序),$p$为从$f$转移到$f'$的概率(则从$f'$转移回$f$的概率也为$p$),w为转移的花费. 最后输出初始位置

【BZOJ2510】弱题 期望DP+循环矩阵乘法

[BZOJ2510]弱题 Description 有M个球,一开始每个球均有一个初始标号,标号范围为1-N且为整数,标号为i的球有ai个,并保证Σai = M. 每次操作等概率取出一个球(即取出每个球的概率均为1/M),若这个球标号为k(k < N),则将它重新标号为k + 1:若这个球标号为N,则将其重标号为1.(取出球后并不将其丢弃) 现在你需要求出,经过K次这样的操作后,每个标号的球的期望个数. Input 第1行包含三个正整数N,M,K,表示了标号与球的个数以及操作次数. 第2行包含N个

[BZOJ 4008][HNOI2015]亚瑟王(期望Dp)

Description 小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑. 他决定,在脱坑之前,最后再来打一盘亚瑟王.既然是最后一战,就一定要打得漂 亮.众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的.作为一个非 洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值.但他已 经多年没写过代码,连 Spaly都敲不对了,因此,希望你能帮帮小 K,让他感受一 下当欧洲人是怎样的体验. 本题中我们将考虑游戏的一个简化版模型. 玩家有一套卡牌,共

【BZOJ-4008】亚瑟王 概率与期望 + DP

4008: [HNOI2015]亚瑟王 Time Limit: 20 Sec  Memory Limit: 512 MBSec  Special JudgeSubmit: 832  Solved: 515[Submit][Status][Discuss] Description 小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑. 他决定,在脱坑之前,最后再来打一盘亚瑟王.既然是最后一战,就一定要打得漂亮.众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的.作为一个