日常训练2025-1-13

P5020 [NOIP2018 提高组] 货币系统

rating：普及+/提高

https://www.luogu.com.cn/problem/P5020

思路

思考一下题目要干什么，原来的货币系统能够表示出一个集合，不能表示出一个集合，现在把货币数量减少之后能表示的集合和不能表示的集合不变——意味着原本的货币系统中有一些货币的存在是不影响表示出的集合的。

那么他们为什么没作用呢？假设能表示出来的货币为 x ，那么 \(x = na_i + ma_j\)，如果这里的 \(a_j = ka_i\)，也就是说\(a_j\)本身就能被 \(a_i\) 表示，那么 \(a_j\)​ 就是不需要存在的。所以本题就是让我们找哪些货币是能被原本有的货币表示出来的，这些货币需要被删掉。

假设现在要看最大的货币能否被表示，那么小的货币有选与不选两种可能，所以考虑背包。因为大的货币都是被小的货币表示，所以先排个序。

\(f[i][j]\)​：使用前 i 个货币能否表示 j 这个面额，那么 j 的最大值应该为数组中的最大值，对应最大背包容量。

状态转移：\(f[i][j] |= f[i-1][j]\)，如果$ j - v[i] >= 0\(，\)f[i][j] |= f[i-1][j-v[i]]$​

最后，如果第 i 个货币 $f[i-1][v[i]] $存在，那么就应该被删除

代码（未优化）

没有优化的原因是优化后只能查看 i == n 时数组中的状态，而我们是需要知道 i 等于其他值时的状态的，所以优化

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n;
	std::cin >> n;

	std::vector<int> v(n+1);
	for (int i = 1; i <= n; i++) std::cin >> v[i];

	std::sort(v.begin(), v.end());

	int V = v[n];
	std::vector f(n+1, std::vector<int>(V+1, 0));

	f[0][0] = 1;

	for (int i = 1; i <= n; i++){
		for (int j = 0; j <= V; j++){
			f[i][j] |= f[i-1][j];
			if (j >= v[i]) f[i][j] |= f[i][j-v[i]];
		}
	}

	int ans = n;
	for (int i = 1; i <= n; i++){
		if (f[i-1][v[i]]) ans -= 1;
	}

	std::cout << ans << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	std::cin >> t;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}

代码（优化）

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAXAI 25005
#define MAXN 105
int f[MAXAI];
int a[MAXN];
int main()
{
    //freopen("money.in","r",stdin);
    //freopen("money.out","w",stdout);
    int i,j,n,T,ans;
    scanf("%d",&T);
    while(T--)
    {
        memset(f,0,sizeof(f));
        scanf("%d",&n);ans=n;
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        f[0]=1;
        for(i=1;i<=n;i++)
        {
            // 此刻的f数组还没有更新刚好表示 i - 1 时的状态。
            if(f[a[i]])
            {
                ans--;
                continue;
            }
            for(j=a[i];j<=a[n];j++)
            {
                f[j]=f[j]|f[j-a[i]];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}