题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

过不了

#include<iostream>
#include<cstring>
using namespace std;

const int N = 110, M = 100010;
int a[N], b[N * 10];
int f[M];
int main()
{
    int n, m;
    while(cin >> n >> m, n || m)
    {
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++) cin >> a[i];
        int cnt = 0;
        for (int i = 1; i <= n; i ++)
        {
            int c;
            cin >> c;
            int k = 1;
            while(k <= c)
            {
                b[cnt ++] = k * a[i];
                c -= k;
                k <<= 1;
            }
            if (c) b[cnt ++] = c * a[i];
        }

        f[0] = 1;
        for (int i = 0; i < cnt; i ++)
            for (int j = m; j >= b[i]; j --)
                f[j] |= f[j - b[i]];

        int  res = 0;
        for (int i = 1; i <= m; i ++) res += f[i];
        cout << res << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 110, M = 100010;
int a[N], b[N];
int f[M], g[M];
int main()
{
    int n, m;
    while(cin >> n >> m, n || m)
    {
        for (int i = 1; i <= n; i ++) cin >> a[i];
        for (int i = 1; i <= n; i ++) cin >> b[i];
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= n; i ++)
        {
            memset(g, 0, sizeof g);
            for (int j = a[i]; j <= m; j ++)
                if (!f[j] && f[j - a[i]] && g[j - a[i]] < b[i])
                {
                    f[j] = 1;
                    g[j] = g[j - a[i]] + 1;
                }
        }

        int  res = 0;
        for (int i = 1; i <= m; i ++)
            if (f[i]) res ++;
        cout << res << endl;
    }
    return 0;
}