acwing 532. 货币系统
原题链接:https://www.acwing.com/problem/content/534/
思路
阅读理解
noip、csp的题先从题中找性质,然后去写
观察样例,不难发现,先给a排序,如果前面的某些个数能够组成后面的数,就把后面的数删掉,得到的就是最优解。(比赛或考试的时候,如果实在证不出来,可以尝试去写了,总比罚座好)
严谨解法:
题中可以发现如下三个性质:
性质1:a1,a2...an可以被b1,b2...bm表示出来。
因为b可以表示a所表示的所有数,所以b一定能表示a,即a[j]=t[i]*b[i]+t[i+1]*b[i+1]...
性质2:b1,b2,...,bm不能被其他bi表示出来
因为m最小,就要找最大独立集({3,10}是{3,6,10,19}的最大独立集)
性质3:在最优解中,b1,b2,b3...bm一定都是从a1,a2,a3...an中选择出来的
反证法证明:假设bi不在a1~an中,bi可以由某些个a表示出来:bi=a1+a2+a3,且bi>a1、a2、a3中的任意一个。a1~an可以由b表示出来,所以bi=t1*b1+t2*b3+...,bi又用b表示出来了,不是最优解了就,所以不成立
最优解是从a中产生的,如果a[i]能被a[1~i-1]表示出来,那么就不选,否则就选。
最后选出的就是解。
注意此题只要不能表示出来就一定要选,并不是贪心,只是一个模拟过程。
具体做法
将a从小到大排序
然后筛一遍,如果ai能被凑出来就不要,否则就res ++
dp分析
f[i][j]
状态表示
集合:f[i][j]表示从前i个选,和为j的方案是否存在。(f[][0] = 1)
属性:bool值,存在就为true,不存在就为false
状态转移
f[i][j]
f[i][j] = f[i-1][j] | f[i-1][j- k*a[i]] => f[j] |= f[j-a[i]]
边界
f[][0] = true
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 25010;
int a[N];
bool f[N];
int t,n;
int main()
{
cin >> t;
while(t --)
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
sort(a+1,a+n+1);
memset(f,0,sizeof f);
int res = 0;
int m = a[n]; // 和最大值
f[0] = true;
for(int i = 1;i <= n;i ++)
{
if(!f[a[i]]) res ++;
for(int j = a[i];j <= m;j ++)
f[j] |= f[j-a[i]];
}
cout << res << endl;
}
return 0;
}
原文地址:http://www.cnblogs.com/rdisheng/p/16835215.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性