这是一道背包问题,主要的难题是计算概率。假设A大学录取的概率为a,B大学录取的概率为b。那么没有被一所大学录取的概率为(1-a)(1-b),所以录取的概率为1-(1-a)(1-b)=a+b-a*b。递推的公式为dp[i]=max{dp[i],dp[i-arr[j]]+prob[i]-dp[i-arr[j]]*prob[i]}。
C++代码如下:
#include<stdio.h> #include<memory.h> const int N=10010; double dp[N]; int arr[N]; double prob[N]; double MAX(double a,double b){ if(a>b) return a; else return b; } int main(){ int n,m;//freopen("1.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){ if(n==0&&m==0) return 0; for(int i=0;i<m;i++) scanf("%d %lf",&arr[i],&prob[i]); memset(dp,0,sizeof(dp)); for(int i=0;i<m;i++){ for(int j=n;j>=arr[i];j--){ dp[j]=MAX(dp[j],dp[j-arr[i]]+prob[i]-dp[j-arr[i]]*prob[i]); } } printf("%.1lf%%\n",dp[n]*100); } return 0; }