专栏文章

P5020 [NOIP 2018 提高组] 货币系统 · 题解

jjcs_pp
P5020题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipnkl07
此快照首次捕获于
2025/12/03 14:55
3 个月前
此快照最后确认于
2025/12/03 14:55
3 个月前
查看原文
P5020

总体思路：

这题让我们给出一个与原货币系统等价的货币系统，分析题目和样例可发现，这其实就是在优化原货币系统。
如何优化呢？
如果一种货币的面额可以用其他货币表示出来，那么他就没有存在的必要了，就可以优化。 例如：样例的第一组数据，优化了 66 和 1919 ，因为 66 可以用 33 表示出来 （6=3+3）（6=3+3） ， 1919 可以用 33 和 1010 表示出来 （19=3+3+3+10）（19=3+3+3+10）
所以我们就找到那些不可以优化（不可以用其他货币表示出来）的货币即可，即求每种面额能被表示几遍，用动态规划中的完全背包。

上代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T,n;
int a[110];
int dp[110][25010];
int mx;
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n;
		mx=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			mx=max(mx,a[i]); 
		}
		for(int i=1;i<=n;i++)//基本完全背包 
		{
			dp[i][0]=1;
			for(int j=1;j<=mx;j++)//求到最大面额的货币就好了 
			{
				dp[i][j]=dp[i-1][j];
				if(j>=a[i]) dp[i][j]=dp[i][j]+dp[i][j-a[i]];
			}
		}
		int ans=0; 
		for(int i=1;i<=n;i++)
		{
			if(dp[n][a[i]]==1) ans++;//剩下的货币 
		}
		cout<<ans<<'\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...