HDU6025 Coprime Sequence
题意：最大化数列中删除掉一个数后的GCD。数列长度n=10^5，T=10
题解：暴力枚举删除每个数，问题转化为O（1）求出数列中剩余数的GCD。
做法是预处理出前缀GCD和后缀GCD，则除去a[i]之外其余数的GCD'[i]=gcd(前缀[i],后缀[i])
期望DP也放在这里吧：
►总结：转移方程有时比较灵活。一般求概率是正推，求期望是逆推。
poj 2096 期望入门题Collecting Bugs
题意：程序的bug有n个子集，s个种类。每一个bug属于每个子集的概率为1/n，每一个bug属于每个种类的概率为1/s，问每个子集且每个种类都有bug的期望。
题解： dp[i][j]表示已经找到i种bug,j个系统的bug，达到目标状态的天数的期望
dp[n][s]=0;要求的答案是dp[0][0];
dp[i][j]可以转化成以下四种状态:
1）dp[i][j],发现一个bug属于已经有的i个分类和j个系统。概率为(i/n)*(j/s);
2）dp[i][j+1],发现一个bug属于已有的分类，不属于已有的系统.概率为 (i/n)*(1-j/s);
3）dp[i+1][j],发现一个bug属于已有的系统，不属于已有的分类,概率为 (1-i/n)*(j/s);
4）dp[i+1][j+1],发现一个bug不属于已有的系统，不属于已有的分类,概率为 (1-i/n)*(1-j/s);
整理便得到转移方程
评论 (0)
