HDU 动态规划（46道题目）倾情奉献~ 【只提供思路与状态转移方程】 - 西风萧瑟@HDU - C++博客
Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=max{f[j],f[j-q[i].v]+q[i].money}(f[j]表示在概率j之下能抢的大洋);
正确的方程是:f[j]=max(f[j],f[j-q[i].money]*q[i].v) 其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前抢劫过;
始化为:f[0]=1,其余初始化为-1 (抢0块大洋肯定不被抓嘛)
最大报销额 http://acm.hdu.edu.cn/showproblem.php?pid=1864
又一个背包问题,对于每张发票,要么报销,要么不报销,0-1背包,张数即为背包;
转移方程:f[j]=max(f[j],f[j-1]+v[i]);
恶心地方:有这样的输入数据 3 A:100 A:200 A:300
Read full article from HDU 动态规划（46道题目）倾情奉献~ 【只提供思路与状态转移方程】 - 西风萧瑟@HDU - C++博客
No comments:
Post a Comment