ACM_JLINE.

NOIP2018提高Day1

DP
字数统计: 678阅读时长: 2 min
2019/03/04 Share

NOIP2018提高Day1 第一题

原题链接：传送门

NOIP普及组整理的差不多，后期课件安排应该挺烦，先来感受一下提高组吧！
一天一题 (最近学习计算机系统中， 这个东西还蛮有意思)

题目大意：

在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n 面额数组为 a[1..n] 的货币系统记作 (n,a)。

在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i] × 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

3 19 10 6 这组数据中， 只要选择 3 和 10 就行了 因为 6 = 3 + 3，19 = 3 + 3 + 3 + 10 ;

解法一：

点破了真的还挺简单，完全背包， 先排个序， 然后只要判断这个数能否从前面已经选贼的数推出，能的话直接跳过；不能那么用这个数取更新后面的数字， 总答案 + 1。

Code block

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int a[105];
int T, ans, n;
int f[25005];

int main(){
    scanf("%d", &T);
    while(T--){
        ans = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
        } 
        
        for(int i = 0; i < 25005; i++){
            f[i] = 0;
        } //没初始化 又wa了一发
        
        sort(a, a + n);
        
        for(int i = 0; i < n; i++){
            if(f[a[i]]) continue;
            f[a[i]] = 1; ans++;
            
            for(int j = a[i]; j <= a[n - 1]; j++){
                if(f[j - a[i]]) f[j] = 1;
            }
        }
        
        printf("%d\n", ans);
    }
    return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/03/04/提高18_01/

发表日期：March 4th 2019, 7:59:22 pm

更新日期：March 4th 2019, 7:58:51 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. NOIP2018提高Day1 第一题
    1. 1.1. 原题链接：传送门
      1. 1.1.1. 题目大意：
        1. 1.1.1.1. 说得花里胡哨的，其实就是将在一堆数中，只有保留几个数就能拼出其他数字
      2. 1.1.2. 样例解释：
      3. 1.1.3. 解法一：
      4. 1.1.4. Code block
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路