1. 题目

传送门= ̄ω ̄=

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

2. 题解

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

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

如果要从状态i转移到状态j,那么必须满足:
1. booki=1
2. fi+1<=C你当前枚举的物平

如果满足的话就转移状态,并且更新fj的值。注意每次枚举物平的时候要把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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *