ACM

HDU - 1466 计算直线的交点数(dp)

HDU - 1466 计算直线的交点数(dp)
题目都是中文的,好懂。一开始当作树形dp去做,wa了,发现有些情况还没考虑到。一下是摘自Even的题解n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,所以n=20的话,最大的交点数是190本题是求有多少种交点数:容易列举出N=1,2,3的情况:00,10,2,3如果已知<N的情况,我们来分析加入第N条直线的情况(这里N=4):1、第四条与其余直线全部... 继续阅读 »
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

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

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]... 继续阅读 »
ACM

zoj 3329 One Person Game(带环概率dp,转化)

zoj 3329 One Person Game(带环概率dp,转化)
题目意思是你现在有三个骰子,die1,die2,die3,如果抛出die1=a,die2=b,die3=c,那么你你的积分清零,否则你的积分加上这个三个骰子之和。求你的积分大于n的期望?这个题比较有意思,就算你想到了递推式也很难想到转化,哈哈。首先我们假定当前积分是i,那么有递推式:E[i] = ∑(E[i+k]*p[k]) + E[0]*p[0] + 1     &... 继续阅读 »
ACM

POJ 3744 Scout YYF I(概率dp,递推,矩阵快速幂)

POJ 3744 Scout YYF I(概率dp,递推,矩阵快速幂)
题意:YYF要深入敌后,现在要经过一条地雷路,这些路上有很多的地雷(这些地雷都是长在地图上的,看得到,不用怕)。然后YYF有p的概率走一步,有1-p的概率跳两步。现在问你他安全走过雷区的概率是多少?自己先在草稿纸上画画就能推出递推式,比如我是这样画的:x ox _ ox _ _ o。。。。。。(注意,题目给的数据必定无序,所以先排序)x代表安全起点,o代表地雷,然后手动模拟概率就可以得出递推式:d... 继续阅读 »
ACM

POJ 2096 Collecting Bugs(概率dp)

POJ 2096 	Collecting Bugs(概率dp)
题目意思是有个人喜欢收集bug,然后现在的收集规则是这样的:一个软件的bug分为n类,软件还有s种子组件,找到一个bug有可能是n种分类中的一种并且还属于s种子组件里面的其中一个组件。问题是求:找出的bug有n种分类并且还存在于s种子组件里面。我们可以定义下一次找到bug的情况的四种概率(i为分类的变量,j为子组件的变量):下一个bug属于已经找到的i种分类,j种子组件 :p1= i*j/n*s;... 继续阅读 »