lightoj 1079 Just another Robbery(期望+01背包)

vj传送门

比较裸了

求期望,发现是一个明显的背包问题

容量和价值都是整数,所以作为$dp$数组的下标

$dp$数组的值就是取到$i$价值的最大安全概率

为什么是安全,因为危险很难算,求对立事件

就非常裸了

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int n,m[maxn]; double p[maxn],dp[maxn]; int main() { int t,casenum=0; cin >> t; while( t-- ) { double P; cin >> P >> n; for(int i=0;i<=10000;i++) dp[i]=-1; dp[0] = 1; for(int i=1;i<=n;i++) { cin >> m[i] >> p[i]; for(int j=10000;j>=m[i];j--) if( dp[j-m[i]]!=-1 ) dp[j] = max( dp[j],dp[j-m[i]]*(1.0-p[i]) );//安全的概率 } for(int i=10000;i>=0;i--) if( dp[i]>(1.0-P) ) { printf("Case %d: %d\n",++casenum,i); break; } } }