ACM

HDU - 1712 ACboy needs your help(DP)

HDU - 1712 ACboy needs your help(DP)
题目意思是给你n节课,m天,接下来给出n行,每行有m个数,代表着第i节课学习j天能获得的价值。求能获得的最大价值。递推式:dp[j] = max(dp[j], dp[j-k]+res[i][k])意思就是学习j天的最大价值是当前价值,还是当前价值减去k天,用这k天来学习新的课程的价值。代码:StatusAcceptedTime93msMemory1772kBLength705LangC++#inc... 继续阅读 »
ACM

CodeForces - 148D Bag of mice(概率dp)

CodeForces - 148D Bag of mice(概率dp)
题目意思是,公主和龙比赛从一个具有w个白老鼠,b个黑老鼠的袋子里拿老鼠出来。如果公主从袋子里拿出白老鼠就算公主赢。但是每次龙拿出一只老鼠时还会跳出一只老鼠,跳出的老鼠不管是黑是白都与这次谁输赢无关,但是如果最后公主都没抓到白老鼠,那么龙赢。设dp[i][j]为目前剩下i只白老鼠,j只黑老鼠时公主赢的概率。那么当j==0时,公主必赢,否则就有几种情况。dp[i][j] = ∑(公主直接拿到... 继续阅读 »
ACM

CodeForces 540D Bad Luck Island(概率dp)

CodeForces 540D Bad Luck Island(概率dp)
题目意思,剪刀,石头,布生活在一起,但是剪刀遇见石头石头会死掉,石头遇见布布会死掉,布遇见剪刀剪刀会死掉。给出你r,s,p分别代表剪刀、石头、布的数量。分别求剪刀石头布存在的概率。设dp[i][j][k]为目前还剩下i个石头,j个剪刀,k个布。此时存活的概率都是1。如果其中一种已经消失,那么剩下两个物种便可以肯定谁会存活。然后循环状态转移:double tot=i*j+j*k+k*i;dp[i-1... 继续阅读 »
ACM

OpenJ_Bailian - 2711 合唱队形(递增子序列)

OpenJ_Bailian - 2711 合唱队形(递增子序列)
很明显的递增子序列,很久没做这种题了,都没往这里想。从前往后扫一遍,从后往前扫一遍然后求最大的,用总数减去最大值即可。代码:StatusAcceptedTime2msMemory200kBLength839#include <iostream> #include <cstdio> using namespace std; con... 继续阅读 »
ACM

FZU - 1492 地震预测(数组模拟链表)

FZU - 1492 地震预测(数组模拟链表)
题目意思很容易懂,就是求当前数与后面数的最小差值的绝对值之和。可以直接用数组模拟链表排序。因为排序完成后离开这个数的最小差值肯定是和左右两边相减取最小值。那么我们记录下原数据在排序后的位置,然后在排序后的位置里面找原数据的第一位,与左右相减肯定是第一个数与后面数的最小差值,然后抹掉这个数,把这个数前面和后面的数连接起来。再去找接下来的第二个数,依次到最后,就是这样。代码:StatusAccepte... 继续阅读 »
ACM

HDU - 4089 Activation(概率dp,迭代)

HDU - 4089 Activation(概率dp,迭代)
题目的意思是,Tomato在排队激活游戏,有四种情况:1、注册失败,但是不影响队列顺序 ,概率为p12、连接失败,队首的人排到队尾,概率为p23、注册成功,队首离开队列,概率为p34、服务器崩溃,激活停止,概率为p4现在给出总排队人数n,Tomato排在第m个,一个数k,然后是四种情况的概率p1-p4;如果Tomato前面在k-1个人之内,并且服务器崩溃了,那么这种情况Tomato认为服务器是很l... 继续阅读 »
ACM

HDU 4336 Card Collector(概率dp,状态压缩)

HDU 4336 Card Collector(概率dp,状态压缩)
题目意思是,收集卡片,收集每张卡片的概率已经给出,并且所有的概率之和小于或等于1,问你收集完所有卡片的零食袋数的期望。这题很6啊,状态压缩,利用二进制的特性来枚举,但是有个坑啊,输出要是保留4位小数啊,题目最后说了啊(the standard answer is no more that 10^-4.)。假设现在一共要收集4张卡。那么:1111就代表收集了4张卡,1001就代表收集到了第一张和第四... 继续阅读 »
ACM

ZOJ 3380 Patchouli's Spell Cards(概率dp,组合数学)

ZOJ 3380 Patchouli's Spell Cards(概率dp,组合数学)
题目的意思是,给你m种元素,他们每个元素有n种不同的相位,如果相位相同则可以组合在一起发动一次魔法攻击(当然,一个也可以)。问你发动一次魔法至少有l种元素组合的概率?首先我是自己想的去找这些可能性,总数比较好找,就是n^m,但是发现当l>m/2时会有重复,而且不好去除。所以就看了题解。。。大家都是按照自己的理解为球填色。我是这样理解的,先画图:各个变量标识和题目意思相同,途中第一条黄色箭头代... 继续阅读 »
ACM

HDU3853 LOOPS(概率dp)

HDU3853 LOOPS(概率dp)
题目意思是一个人要拯救世界,穿过一个迷宫才可以。这个迷宫分为R*C个房间。你在每个房间里面施放一次魔法消耗两点魔法能量,然后有一定的概率在原地呆着,有一定概率往右走,有一定概率往下走。问你最后走出迷宫消耗魔力的期望值。简单dp,递推式:dp[i][j] = dp[i][j]*p[0] + dp[i+1][j]*p[1] + dp[i][j+1]*p[2];dp[i][j]代表当前处于第i行第j个格... 继续阅读 »
ACM

HDU 4405 Aeroplane chess(概率dp)

HDU 4405 Aeroplane chess(概率dp)
题目意思就是,你在下一盘飞行棋,飞行棋大家都下过吧。现在有n个点从1-N标号,你在0点,给你一个骰子,你抛出得到一个值就可以走到当前坐标+骰子的值的位置。但是有些地方是可以飞过去的。现在给出这些飞过去的坐标,问你走到终点n或者n+投骰子的期望?我们可以用一个数组保存航班信息,fly[i]=j,代表从i可以飞到j。同样扔出点数为x的概率为p,也就是1/6,递推式是:dp[i] = dp[fly[i]... 继续阅读 »