1. 题目

传送门=￣ω￣=

题意：给你 n 种硬币，第 i 种的面值是 ai，个数时 ci，求这些硬币能凑成区间 $[1,m]$间的那些值

2. 题解

普通的多重背包复杂度为 $O(n\times m\times c)$显然超时
二进制优化复杂度大致刚好卡在 1e8 的复杂度上，多组数据就挂了
只能用 $O(n\times m)$的复杂度了

这题又没有背包容量限制，只有每种硬币个数限制
我们循环的第一层枚举使用那种硬币，设 f_i 表示当背包容量为 i 的时候，当前枚举的物平最少的使用次数，默认都为 0。
再设 book_i 表示（全局）能否达到总面值 i，等于 1 表示能，等于 0 表示不能

如果要从状态 i 转移到状态 j，那么必须满足：
1. book_i=1
2. f_i+1<=C _{你当前枚举的物平}

如果满足的话就转移状态，并且更新 f_j 的值。注意每次枚举物平的时候要把 f 全设为 0

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,a[105],c[105],ans,f[100005];
bool book[100005];
int main()
{
    while(IN(n),IN(m),memset(book,0,sizeof(book)),book[0]=1,ans=0,n|m)
    {
        for(int i=1;i<=n;i++)IN(a[i]);
        for(int i=1;i<=n;i++)IN(c[i]);
        for(int i=1;i<=n;i++)
        {
            memset(f,0,sizeof(f));
            for(int j=a[i];j<=m;j++)
                if(f[j-a[i]]<c[i]&&book[j-a[i]])
                    if(!book[j]||f[j]>f[j-a[i]]+1)f[j]=f[j-a[i]]+1,book[j]=1;
        }
        for(int i=1;i<=m;i++)ans+=book[i];
        printf("%d\n",ans);
    }
    return 0;
}