题目描述

blablabla

样例

blablabla

算法1

(DP) $O(N*M)$

blablabla

思路:

这题并不是很难,无非在自己可行的模式中做一次完全背包,这样就可以保证复杂度达到O(1),然后这题就解决了.当然这个完全背包并不是真正的完全背包,我们还是要判断下是否可行,毕竟它有数量限制.如此,我们不妨设两个数组,一个f标记这个硬币能不能用前面的硬币组合得到,第二个cnt记录我假如能达到这个状态需要多少这种硬币.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e3+5;
bool f[N];
int a[N],c[M],cnt[N];//价值 数量
int main()
{
    int n,m;f[0]=true;
    while(cin>>n>>m)
    {

        int ans=0;
        for(int i=1;i<=m;i++)   f[i]=false;
        if(!n&&!m) break;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&c[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)   cnt[j]=0;
            for(int j=a[i];j<=m;j++)
            {
                if(!f[j]&&cnt[j-a[i]]<c[i]&&f[j-a[i]])//合法即可转移.
                {
                    cnt[j]+=cnt[j-a[i]]+1;
                    f[j]=true;
                }
            }
        }
        for(int i=1;i<=m;i++)
        {
            if(f[i])    ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}