hdu2955 robberies題解（01背包）

注意要先轉換成不被抓的機率再來算

狀态轉移方程money[k]=max(money[k],money[k-M[i]]*p[i])//這裡的p[i]是不被抓的機率。

#include <stdio.h>
#include <string.h>
#define Max(X,Y) ((X)<(Y)?(Y):(X))
double money[];
int main(int argc, char const *argv[])
{
    double P,p[];
    int T,N,M[],i,k,maxn;
    scanf("%d",&T);
    while(T--){
        scanf("%lf %d",&P,&N);
        maxn=;P=-P;//不被抓的機率
        for(i=;i<N;i++){scanf("%d %lf",M+i,p+i);maxn+=M[i];p[i]=-p[i];}
        memset(money,,sizeof(money));
        money[]=;
        for(i=;i<N;i++)
            for(k=maxn;k>=M[i];k--)
                if(money[k-M[i]]*p[i]>=P)
             money[k]=Max(money[k],money[k-M[i]]*p[i]);
        for(k=maxn;k>=;k--)
            if(money[k]>=P) {printf("%d\n",k );break;}
    }
    return ;
}