永怀善意 清澈明朗。
### LDU DP1（3.8场） lduicpc
A - Robberies HDU - 2955
很典型的背包问题，但这里要做一个转化。
我们进行状态转移方程时用不被抓的概率进行计算，因为如果不被抓的话，说明之前包括这次都不被抓。
把不被抓的概率看作是体积，把可获得的金钱看成价值，就转化成了01背包问题。dp[i]表示偷到 i 的金钱不被抓的概率，可推出状态转移方程如下：
for(int i=1;i<=n;i++) for(int j=sum;j>=m[i];j--) dp[j]=max(dp[j],dp[j-m[i]]*p[i]);
最后遍历输出即可。
具体细节见代码叭
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> PII; #define I_int ll #define PI 3.1415926535898 inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); puts(""); } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7,inf=1e9,mod=1e9+7; double p[maxn],dp[maxn]; int m[maxn]; int t,n; double P; ///dp[i]表示偷到i不被抓的概率 ///01背包 把钱数看成价值，不被抓的概率看成体积 int main(){ t=read(); while(t--){ cin>>P>>n; int sum=0; for(int i=1;i<=n;i++){ cin>>m[i]>>p[i]; p[i]=1-p[i]; sum+=m[i]; } memset(dp,0,sizeof dp); dp[0]=1; for(int i=1;i<=n;i++) for(int j=sum;j>=m[i];j--) dp[j]=max(dp[j],dp[j-m[i]]*p[i]); P=1-P; for(int i=sum;;i--) if(dp[i]>P){ cout<<i<<endl; break; } } return 0; }
其他的题都是板子题，就不写题解了（强行解释）
