HDU 1203（dp46）

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; double dp[10005]; struct node { int money; double pro; }school[10005]; int main() { int n,m; while(scanf("%d%d",&n,&m)) { if(n==0&&m==0) return 0; int i,j; double temp; for(i=1;i<=m;i++) { scanf("%d %lf",&school[i].money,&temp); school[i].pro=1.0-temp;//转换成不被录取的概率，最后输出的时候拿1减 } for(i=0;i<=n;i++) dp[i]=1.0;//一定要注意这个初始化必须为1.0，因为不花钱就是百分百不会被录取，而且下面是一个min函数要保证初始值比真实值大 for(i=1;i<=m;i++) for(j=n;j>=school[i].money;j--) dp[j]=min(dp[j],dp[j-school[i].money]*school[i].pro); printf("%.1f%%\n",100*(1.0-dp[n]));//输出注意格式 } return 0; }