Luogu5020 货币系统

发布于 2020-09-03  51 次阅读


LInk

About

为什么要写这一题的题解,即便这是一道背包题

因为Tony的NOIP2018断送在了这一道题上面

我深刻的记得

那是一个秋天,NOIP2018比赛日Day1,长沙理工大学,微冷,小雨

读了T2,我坚决相信这是一道数学题,当时写了筛法还是什么的吧

CJOIer2017张隽宇是我的学长,我们叫他学哥,当时出来的时候还跟他交流了一下发现也写的是筛法,信心满满

然后Boom0

害,也许是印象深刻才会再写这道题,再写这篇题解,再把那年的故事写下来吧

nia我屁话好多

Solution

当年真的写的筛法来着

其实duck不必

$a[i]$的范围就在$25000$以内,我们要看一个数可不可以被货币系统内的数表示出来,可以搜也可以跑完全背包

f[i]表示if[i]种方法表示

我们可以写出如下的转移f[j] = max{f[j - v[i]] + 1}

相当于记下一个数可以最多有多少种方法表达

假如一个数在货币系统中只有一种表达,很显然我们需要这个数,答案更新

Code

短短的题解,多多的废话,又到了我最喜欢的代码环节

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

const int SIZE = 1e3 + 5;

int T, n, ans = 0;
int v[SIZE], m[SIZE], f[30005];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    T = read();
    while (T--) {
        n = read();
        for (int i = 1; i <= n; i++) 
            v[i] = read();
        memset(f, -0x3f, sizeof(f)); 
        f[0] = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= 25000; j++) {
                f[j] = std::max(f[j], f[j - v[i]] + 1);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (f[v[i]] == 1) ++ ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

朴实沉毅