打卡

C++ 代码

//E.Coins

/*
f[j](0或1) 表示在i阶段中能否拼出面值为j的情况；
由于本题仅关注“可行性”(面值是否能拼成)而非“最优性”所以根据动态规划的过程我们可以发现，
若前i种硬币能拼成面值j，那么只有两种可能的情况
1
前i-1种硬币就能拼成面值j，即在第i阶段开始前，f[j]已经成为1。
2
使用了第i种硬币，即在第i阶段的递推过程中，发现f[j-v[i]]为1，从而使用一个i硬币，使f[j]变为1。
于是可以考虑一种贪心策略：设g[j]表示在第i阶段下将f[j]变为1至少需要使用多少枚第i种硬币。
为了满足我们的贪心策略，我们应该尽量多的使用第1种情况,也就是说在f[j-a[i]]为1时，若f[j]已经为1，
就不进行DP转移,并令used[j]=0(我们并没有使用第i种硬币)
仅当f[j-v[i]]为1而f[j]为0且已经使用的i硬币g[j-v[i]]<c[i]时,
我们使用一个i硬币使f[j]变为1,g[j]=g[j-v[i]]+1;

*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110;
const int M = 1e5+10;

int n,m;
int v[N],s[N];
int f[M],g[M];
//g[j]j之前(包括j)的最近的一个1的距离


int main()
{
    while(scanf("%d%d",&n,&m), n || m)
    {
        for(int i = 1; i <= n; i++) scanf("%d",&v[i]);
        for(int i = 1; i <= n; i++) scanf("%d",&s[i]);

        memset(f, 0, sizeof(f));
        f[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            memset(g, 0, sizeof(g));
            for(int j = v[i]; j <= m; j++)
            {
                if(!f[j] && f[j - v[i]] && g[j - v[i]] < s[i])
                {
                    f[j] = 1;
                    g[j] = g[j - v[i]] + 1;
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= m; i++)
        {
            ans += f[i];
        }
        printf("%d\n",ans);
    }


    return 0;
}