HDU-2844-Coins(多重背包)

#include <cstdio>
#include <algorithm>
using namespace std;

int d[105],c[105],dp[100005];

int main()
{
    int n,m,i,j,k,ans;

    while(~scanf("%d%d",&n,&m) && n+m)
    {
        for(i=0;i<n;i++) scanf("%d",&d[i]);
        for(i=0;i<n;i++) scanf("%d",&c[i]);

        for(i=0;i<=m;i++) dp[i]=0;

        for(i=0;i<n;i++)
        {
            if(d[i]*c[i]>=m)
            {
                for(j=d[i];j<=m;j++) dp[j]=max(dp[j],dp[j-d[i]]+d[i]);
            }
            else
            {
                k=1;

                while(((k<<1)-1)<=c[i])
                {
                    for(j=m;j>=k*d[i];j--) dp[j]=max(dp[j],dp[j-k*d[i]]+k*d[i]);

                    k<<=1;
                }

                if(k-1<c[i])
                {
                    k=(c[i]-k+1)*d[i];

                    for(j=m;j>=k;j--) dp[j]=max(dp[j],dp[j-k]+k);
                }
            }
        }

        ans=0;

        for(i=1;i<=m;i++) if(dp[i]==i) ans++;

        printf("%d\n",ans);
    }
}