洛谷 P2473 题目解答:f[i][j] 表示的是进行了前 i 轮,物品集合为 j(不包含本轮的) 的期望值。这里的 j 相当于一种预估,是一种前继的记录。
如果直接用 f[i][] 去转移 f[i+1][],会出问题,如果 f[i][j] 这种情形本来就不可能存在,那么其转移也都是不合法的。所以就倒推,倒推时不合法的依然可能存在,但是方程中取 max 的时候做了裁决,不合法的状态此时一定会被舍掉。
枚举 i、枚举 j、枚举这轮选的物品 now(虽然是这轮选的,但是根据我们的状态设计,它所对应的那个二进制 1 会被记到 f[i+1][] 里)。
如果 j 中具备了选择 now 的条件,f[i][j]+=max{f[i+1][j],f[i+1][j|(1<
否则 f[i][j]+=f[i+1][j]/N
为了减小精度误差,÷N 可以放到最后。
代码
- //期望dp、状压dp #include #include #define maxn 15#define maxk 110using namespace std;int K, N, pre[maxn+5];double f[maxk][1<
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/03-17/18941914.html