洛谷P5020题解

原题

P5020 [NOIP2018 提高组] 货币系统

思路概述

题意分析

给定包含一个整数 \(n\) 和一个正整数集合 \(a\) 的货币系统 \((n,a)\)，要求将其化简，输出最简的货币系统中的面值数量。其中，化简在货币系统 \((n’,a’)\) 中，任意被原货币系统 \((n,a)\) 表示出的面值都能被表示，任意不能被原货币系统表示的面值相应地不能被表示；最简即 \(n’\) 最小。

思路简述

死去的小凯开始攻击我。

乍一看有点像小凯的疑惑这道题，但是本题的思路与其有一定差别。

由于要求使简化结果中 \(n’\) 尽量小，所以不难知道，若原整数集合中出现 \(\exists a_i∈a,a_i={k_1a_1+k_2a_2\dots k_{i-1}a_{i-1}}\) 的情况，就可以将 \(k\) 约去。

因此只需要枚举上述能被约去的面值，即可得到最简的货币系统。

算法实现

关于枚举

由于本题数据规模是 \(1≤a_i≤25000\),所以可以采用类似质数筛的线性标记法。需要注意的是，区别于质数筛，本题需要从一个已经可以凑出的面额上再累加枚举的面值，即：

当出现当前选定的面额 \(i\) 出现 \(v_i=1\) 的情况，则说明 \(i\) 是可以被简化的面额，因此减小 \(n’\)。

关于标记

特殊地，由于所有面额的货币数量均为 \(0\) 时，可以凑出面额 \(0\)，因此标记数组初始化时就需要令 \(v_0=0\)。

AC code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<set>
#include<ctime>
#define RI register int
using namespace std;
const int maxn=1e2+10,maxsize=5e5+10;
int T,n,lim,ans;
int a[maxn];
bool v[maxsize];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(cin >> T;T;--T)
	{
		memset(v,0,sizeof(v));
		cin >> n;ans=n;lim=0;
		for(RI i=1;i<=n;++i) 
		{
			cin >> a[i];
			lim=max(lim,a[i]);
		}
		sort(a+1,a+n+1);
		v[0]=1;
		for(RI i=1;i<=n;++i)
			if(!v[a[i]])
			{
				for(RI j=0;j<=lim;++j)
					if((!j) || (v[j]))
						for(RI k=1;j+a[i]*k<=lim && !v[j+a[i]*k];++k)
							v[j+a[i]*k]=1;
			}
			else --ans;
		printf("%d\n",ans);
	}
	return 0;
}

原文地址：http://www.cnblogs.com/frkblog/p/16817262.html