P2347 砝码称重

Link

Solution

枚举每个砝码、每个砝码个数和重量从1000到1，如果f[k]可以达到，那么f[k+w[i]]也可以达到，最后把可达到的重量加起来即是答案，可以使用bitset，左移w[i]即指可达到i+w[i]，再与之前总状态取并集即可。

Code

#include <iostream>
#include <bitset>
const int maxn = 1000 + 10;
using namespace std;

int a[6], w[6] = { 1,2,3,5,10,20 };
bitset<maxn> s;

int main() {
    s[0] = 1;
    for (int i = 0; i < 6; i++)cin >> a[i];
    for (int i = 0; i < 6; i++)
        for (int j = 1; j <= a[i]; j++)s |= s << w[i];
    cout << "Total=" << s.count() - 1 << endl;
    return 0;
}

int a[6], w[6] = { 1,2,3,5,10,20 }, f[maxn];

int main() {
    int ans = 0;
    f[0] = 1;
    for (int i = 0; i < 6; i++)cin >> a[i];
    for (int i = 0; i < 6; i++)
        for (int j = 1; j <= a[i]; j++)
            for (int k = 1000; k >= 0; k--)
                if (f[k])f[k + w[i]] = 1;
    for (int i = 1; i <= 1000; i++)if (f[i])ans++;
    cout << "Total=" << ans << endl;
    return 0;
}