题目大意

题意

分析

分析

结论题

结论就是对 1∼200001 \sim 20000 的钱数做完全背包

再与小 tt 的贪心取法比较

Code

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
void sol(){
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 0;i <= 20004;i++) f[i] = inf;
    f[0] = 0;

    for(int i = 1;i <=n;i++){
        for(int j = a[i];j<=20000;j++){
            f[j] = min(f[j],f[j-a[i]]+1);
        }
    }
    //for(int i = 1;i <= 10;i++) cout << f[i] << endl;
    for(int i = 1;i <= 20000;i++){
        int cot = 0;
        int t = i;
        for(int j = n;j>=1;j--){
            cot += t / a[j];
            t = t%a[j];
        }
        if(cot > f[i]){
            puts("No");
            return;
        } 
    }
    puts("Yes");
}

拓展