刷题记录:牛客NC21467[NOIP2018]货币系统

传送门:牛客

题目描述:

在网友的国度中共有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为
了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。
在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n
个非负整数t[i] 满足a[i] x t[i] 的和为x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x
不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。
两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个货币系统表出，要
么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b)，满足(m,b) 与原来的货币系统(n,a)等
价，且m尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的m。
输入:
2
4
3 19 10 6
5
11 29 13 19 17
输出:
2
5

一道有点思维难度的dp吧.牛客怎么才2星…,洛谷上好歹绿题

主要思路:

1. 首先我们需要简化我们的题目.题中要求我们选取两个等价的货币系统.我们思考一下,假设我们已经有了一个货币系统,那么假设我们的这个货币系统中的数字能由该货币系统中的其他数字组合的话.那么是不是我们的当前的这个数字就是多余的了.那么是不是我们就可以拥有一个更加精简的货币系统
2. 总结一下也就是我们尽量的判断我们的数字是否能被其他数字组成,如果能被组成的话就将我们的长度减一即可
3. 对于数字判重问题呢,我们可以使用$f[i]来记录当前的数字能否被组成$,转移方程也很好推,若我们当前的数字是能被组成的,那么我们从第一位开始累加我们的货币系统中的其他数字,累加出来的数字显然也是能被组成的(包括自己).对于最后的答案我们只要判断一下我们的货币系统中的每一个数字能否被组成即可
4. 注意为了保证正确性,我们需要进行排序

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int T;int a[1000];int f[26000];
int main() {
	T=read();int n;
	while(T--) {
		memset(f,0,sizeof(f));
		memset(a,0,sizeof(a));
		n=read();
		for(int i=1;i<=n;i++) {
			a[i]=read();
			f[a[i]]=1;
		}
		sort(a+1,a+n+1);
		for(int i=a[1];i<=a[n];i++) {
			if(f[i]) {
				for(int j=1;j<=n;j++) {
					if(i+a[j]<=a[n]) {
						f[i+a[j]]=2;
					}else {
						break;
					}
				}
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++) {
			if(f[a[i]]==1) {
				ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}