首页 > 代码库 > 01背包水题篇之 HDU2955——Robberies
01背包水题篇之 HDU2955——Robberies
原来是想dp[i],表示不被抓概率为i所能抢到的最大钱(概率1-100)
后来看了别人的博客是dp[i]表示抢了i钱最大的不被抓概率,嗯~,弱菜水题都刷不动。
那么状态转移方程就是
dp[i]=max(dp[i],dp[i-money]*p),初始化dp(0~maxn)为0,dp[0]=1(1毛钱都没抢你抓个毛线啊,哥是良民~)
又是贴代码环节~
<span style="font-size:18px;">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; double dp[11000]; struct node { int m; double p; }a[110]; int main() { int T; cin>>T; while(T--){ double p; int n,sum=0; cin>>p>>n; for(int i=0;i<n;i++){ cin>>a[i].m>>a[i].p; a[i].p=1-a[i].p; sum+=a[i].m; } memset(dp,0,sizeof dp); dp[0]=1; for(int i=0;i<n;i++){ for(int j=sum;j>=a[i].m;j--){ dp[j]=max(dp[j],dp[j-a[i].m]*a[i].p); } } int cnt; for(cnt=sum;cnt>=0&&1-dp[cnt]>p;cnt--); cout<<cnt<<endl; } return 0; } </span>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。