虚灵大盗拉法姆
题目：
Description
加尔鲁什·地狱咆哮看虚灵大盗拉法姆不顺眼已经很久了，终于一天，加尔鲁什·地狱咆哮带着自己的手下恐怖的奴隶主堵住了虚灵大盗拉法姆，虚灵大盗拉法姆拉法姆见势不妙，掏出神器死亡丧钟准备还击。场面十分壮观，如图（略）
已知恐怖丧钟每一发击中敌方单位都将令对方的生命值减一，且击中每个敌方单位的概率是相等的。而恐怖的奴隶主有3点生命值，当其在场上受到非致命伤害且场上恐怖的奴隶主总数小于7时会召唤一个新的3点生命值的恐怖的奴隶主，受到致命伤害（受到攻击后生命为0）时则会直接死去。如场上有1个生命值为3的“恐怖的奴隶主”，当恐怖丧钟打中他时，他的生命值变为2，且召唤一个新的奴隶主。而当恐怖丧钟击中加尔鲁什时，恐怖的奴隶主只会强力围观却什么都不会做。
现知，恐怖丧钟共计会发射X次，加尔鲁什有Y点体力值，而他手下共有Z名生命值为三的奴隶主。问在死亡丧钟使用完毕后，有多大的概率杀死加尔鲁什？（答案保留小数点后6位）
Input
多组数据，第一行有一个整数T，表示有T组数据。（T<=100）
以下T行，每行有三个整数X,Y和Z。(1<=X,Y<=20,0<=Z<=7)
Output
一个小数（保留小数点后六位）。
Sample Input
4 1 1 1 2 1 1 2 1 2 2 2 2
Sample Output
0.500000 0.666667 0.500000 0.111111
这个题目思路倒不复杂，就是记忆化搜索。
用了一个很有趣的东西来简化了一点点代码：(z1 + z2 + z3 < 7)的值是1或者0，true对应1，false对应0。
代码：
#include<iOStream>
#include<string.h>
#include<iomanip>
using namespace std;
double list[21][21][8][8][8];
double f(int x, int y, int z1, int z2, int z3)
{
if (list[x][y][z1][z2][z3] >= 0)return list[x][y][z1][z2][z3];
if (y == 0)return 1;
if (x < y)return 0;
double p1 = f(x-1, y - 1, z1, z2, z3);
double p2 = 0, p3 = 0, p4 = 0;
if(z1)p2 = f(x-1, y, z1 - 1, z2, z3);
if(z2)p3 = f(x-1, y, z1 + 1, z2 - 1, z3 + (z1 + z2 + z3 < 7));
if(z3)p4 = f(x-1, y, z1, z2 + 1, z3 - 1 + (z1 + z2 + z3 < 7));
list[x][y][z1][z2][z3] = (p1 + p2*z1 + p3*z2 + p4*z3) / (1 + z1 + z2 + z3);
return list[x][y][z1][z2][z3];
}
int main()
{
int cas;
cin >> cas;
int x, y;
int z1, z2, z3;
while (cas--)
{
cin >> x >> y >> z3;
z1 = z2 = 0;
memset(list, -1, sizeof(list));
cout << fixed << setprecision(6) << f(x, y, z1, z2, z3) << endl;
}
return 0;
}因为 f 写的很精确，几乎没法再变快了，所以这个题目0ms完美AC
文章最后发布于: 2016-07-31 16:09:21
相关阅读
温馨提示：本scrapy 实战，教大家爬取整个妹纸网站，妹纸4000多，图片10W多，合计10G多数据量……故取名曰：《Scrapy采花大盗小爬虫实战之：勾
知道创宇的pocsuite3更新了。 https://github.com/knownsec/pocsuite3 一、安装 安装p'ython3.4以上 pip3 install pocsuite3 安
产品经理的工作关键，就是准确的抓住用户的需求，恰当的将需求转化为产品，让用户真真切切的解决自己的痛点问题。产品经理整个职业生涯
https://nba.stats.qq.com/playoffs/
常常逛外设天下的坛友们都知道，每到年底、年初，外设天下都会推出一些年度横评、年度盘点类的评测供大家参考、回顾。