硬币(coin)

//尝试拿bitset写 写了好久就是不对

Solution:

大意是 n个硬币 分别扔掉每一个 可以表示出多少种价值
注意每一个可以买到的价值都并不是 只可以有那一种构成情况 比如 1 2 可以构成 3 3也可以构成3 把3删掉之后其实还是可以构成3的

Code:

#include <bitset>
#include <cstdio>
using namespace std;
const int N = 300001;
int n, ans, a[301], f[N];
int main(){
    int n; scanf("%d", &n); f[0] = 1;
    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
        for(int j = N; j >= a[i]; -- j)
            f[j] += f[j - a[i]];
    }
    for(int i = 1; i <= n; ++ i) {
        for (int j = a[i]; j <= N; ++ j) 
            f[j] -= f[j - a[i]]; ans = 0;
        for(int j = 1; j <= N; ++ j)
            if(f[j]) ++ ans; printf("%d\n", ans);
        for(int j = N; j >= a[i]; -- j)
            f[j] += f[j - a[i]];
    }
    return 0;
}
点赞

发表评论

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