题目描述

blablabla

样例

blablabla

算法1

$O(6 * sum)$

我看了看题解, 貌似没用硬币那道题的思路就写一下

首先明显是多重背包,而且是可行性问题,最基本的背包思路是

bool f[10005];
memset(f, 0, sizeof);
f[0] = 1;
for (int i = 1; i <= 6; ++i)
    for (int j = 1; j <= a[i]; ++j)
        for (int k = m; k >= a[i]; --k)
            f[k] |= f[k - a[i]];
if (f[sum/2]) ...;
else ...;

必定超时, 但是这道题是可行性为题, 不需要最优解
我们发现,若前i种石头能凑出 sum/2, 只有两种情况:
1.在i阶段之前, 就已经f[j] = true
2.在i阶段之前, 就已经f[j - i] = true

于是,可以贪心, 设used[j] 表示f[j]在阶段i是为true的情况下至少需要多少块i种石头
这样上面的代码 for(j) for(k) 循环可以优化为1维,直接正序扫面
当(!f[j] && f[j - i] && used[j - i] < a[i])才可以转移

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int p = 10005;

int a[7], used[p << 1];
bool f[p];

int main()
{
    while (true)
    {
        a[0] = 0;
        for (int i = 1; i < 7; ++i) 
            cin >> a[i], a[0] += a[i] * i;

        if (a[0] == 0) break;
        if (a[0] & 1) { cout << "Can't\n"; continue; }
        memset(f, 0, sizeof f);
        a[0] >>= 1; f[0] = 1;

        for (int i = 1; i < 7; ++i)
        {
            for (int j = 0; j <= a[0]; ++j) used[j] = 0;

            for (int j = i; j <= a[0]; ++j)
                if (!f[j] && f[j - i] && used[j - i] < a[i])
                    f[j] = 1, used[j] = used[j - i] + 1;
        }

        if (f[a[0]]) cout << "Can\n";
        else cout << "Can't\n";
    }
    return 0;
}

优化空间

const int N = 2.1e5 + 5;

int n, m, _, k, cas;
int a[7], c[6];
bool f[N];

int main() {
    IOS;
    while (cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> a[6], a[1] || a[2] || a[3] || a[4] || a[5] || a[6]) {
        memset(f, 0, sizeof f); f[0] = 1;
        int s = a[1] + a[2] * 2 + a[3] * 3 + a[4] * 4 + a[5] * 5 + a[6] * 6;
        for (int i = 1; i <= 6; ++i, memset(c, 0, sizeof c)) rep (k, i, s >> 1) {
            c[k % i] = f[k] ? 0 : c[k % i] + 1;
            if (f[k - i] && c[k % i] <= a[i]) f[k] = 1;
        }
        cout << (!(s & 1) && f[s >> 1] ? "Can\n" : "Can't\n");
    }
    return 0;
}