lightoj 1233 - Coin Change (III) 多重背包+二進制優化

n種硬币每種硬币有不同的面值，數量為c[i]，問1-m裡面有多少個價值可以被這些硬币組成...

這個題範圍似乎比上一道範圍差不多但是時限給了2s...上一題的二進制優化多重背包跑了1.4s..這個題跑1.1s...

單純的二進制優化的多重背包，很裸...

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mod 100000007
#define inf 0x3f3f3f3f
int dp[120000];
int a[200],c[200];
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        int n,s;
        scanf("%d %d",&n,&s);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&c[i]);
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            int tmp=a[i];
            for(int k=1;k<=c[i];k=k*2)
            {
                for(int j=s;j>=tmp;j--)
                {
                    dp[j]=max(dp[j],dp[j-tmp]);
                }
                c[i]-=k;
                tmp=tmp*2;
                if(tmp>s)
                    break;
            }
            if(c[i]==0||tmp>s) continue;
            tmp=c[i]*a[i];
            for(int j=s;j>=tmp;j--)
                dp[j]=max(dp[j],dp[j-tmp]);
        }
        int ans=0;
        for(int i=1;i<=s;i++)
            if(dp[i])
            ans++;
        printf("Case %d: %d\n",cas,ans);
    }
    return 0;
}