zoj 1366 Cash Machine

#include <iostream>#include <stdio.h>#include <string.h>using namespace std;const int MC=1e5+5;const int MN=13;int num[MN];int bill[MN];int dp[MC];int ZO(int bill,int cash){    for(int i=cash;i>=bill;i--)        dp[i]=max(dp[i],dp[i-bill]+bill);}int CP(int bill,int cash){    for(int i=bill;i<=cash;i++)        dp[i]=max(dp[i],dp[i-bill]+bill);}void MP(int i,int cash){    if(bill[i]*num[i]>=cash)    {        CP(bill[i],cash);        return;    }    int k=1,M=num[i];    while(k<M)    {        ZO(bill[i]*k,cash);        M-=k;        k*=2;    }    ZO(bill[i]*M,cash);}int main(){    int cash;    int n;    while(scanf("%d%d",&cash,&n)!=EOF)    {        memset(dp,0,sizeof(dp));        for(int i=1;i<=n;i++)        { scanf("%d%d",&num[i],&bill[i]);        }        if(cash==0||n==0)        { printf("0n"); continue;        }        for(int i=1;i<=n;i++) MP(i,cash);        printf("%dn",dp[cash]);    }    return 0;}