题解：P5020 [NOIP2018 提高组] 货币系统

运用算法：贪心和完全背包。

思路

首先直接求

(m,b)

是比较困难的。所以先考虑从

(n,a)

中减去一些多余的面额。
那什么面额是多余的呢，当一个数值

a_i

能被比它小的面额表示时，那么它的存在就没有意义了。
那么有没有

k \in (m,b)

并且

k \notin (n,a)

呢，有两种情况：

$k$ 可以被 $a_i$ 表示出来，那么此时的 $k$ 就没有存在意义了。
$k$ 不可以被 $a_i$ 表示出来，那么原本不能被 $(n,a)$ 表示出来的面额被 $(m,b)$ 表示出来了，不符合题目中的 $(n,a)$ 与 $(m,b)$ 等价。

所以，根据以上推论，我们可以得到

(m,b)\in (n,a)

。则我们可以在

a

上做一次完全背包，时间复杂度可以通过本题。

AC code

CPP

#include<bits/stdc++.h>
using namespace std;
int a[105],dp[25005],n,T;
int solve(int a[],int n){
	int ans=n;
	sort(a+1,a+n+1);
	int p=1;
	for(int i=1;i<=a[n];i++) dp[i]=0;
	for(int i=1;i<=a[n];i++){
		for(int j=1;a[j]<i;j++){
			if(dp[i-a[j]]) dp[i]=1;
		}
		if(dp[i]==0){
			if(i==a[p]) ++p,dp[i]=1;
		}else if(i==a[p]) ++p,--ans;
	}
	return ans;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		cout<<solve(a,n)<<endl;
	}
	return 0;
}

题解：P5020 [NOIP2018 提高组] 货币系统

文章操作

思路

AC code

相关推荐

评论

题解：P5020 [NOIP2018 提高组] 货币系统