DP方程:dp[j]=max(dp[j],dp[j-m[i]]*p[i]);
#include<iostream> #include<stdio.h> #include<string.h> #include<string> using namespace std; double dp[10005]; int m[105]; double p[105]; int main() { int T; scanf("%d",&T); while(T--) { double P; int N; scanf("%lf%d",&P,&N); P=1.0-P; memset(dp,0,sizeof(dp)); //初始化数据 dp[0]=1; int sum=0; for(int i=1;i<=N;++i) { scanf("%d%lf",&m[i],&p[i]); p[i]=1-p[i]; sum+=m[i]; } //DP for(int i=1;i<=N;++i) for(int j=sum;j>=m[i];--j) dp[j]=max(dp[j-m[i]]*p[i],dp[j]); for(int i=sum;i>=0;--i) if(dp[i]>=P) { printf("%d/n",i); break; } } return 0; }
