【Solution】[NOI Online #1 入门组] 文具订购-DP

Posted on | In ,

题目传送门。

分类讨论

可以枚举三个数中最小的

下面以 $a$ 最小的情况为例

  • $\because 7a+4b+3c=n$
  • $\therefore 7a=n-4b-3c$
  • 由于我们要考虑 $a+b+c$ 最大. 因为 $b$ 的系数比 $c$ 要大, 而和为定值, 所以当 $a$ 固定时, $b$ 越小越好
  • 所以我们就可以令 $b$ 为 $a, a+1, a+2$ 中的一个(为了满足 $c$ 是整数, 找一个值使得 $n-4b-7a \equiv 0 \pmod {3}$)

将上面的方法重复套到 $b$ 和 $c$ 中, 跑三遍 for (有点丑)即可

最后然后别忘了校验得出来的值是否合理

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <iostream>

#define min3(a, b, c) std::min(std::min(a, b), c)

const int coeff_a = 7, coeff_b = 4, coeff_c = 3;

int main()
{
    int n;
    int ans_a = -1, ans_b = -1, ans_c = -1;

    scanf("%d", &n);
    
    for (int a = 0; a <= n; a++) // a <= b, c
    {
        int b = a, c;
    
        while (((n - a * coeff_a - b * coeff_b) % coeff_c + coeff_c) % coeff_c != 0)
            b++;
        c = (n - a * coeff_a - b * coeff_b) / coeff_c;
    
        if (c < 0 || c < a)
            break; // 矛盾
    
        if (min3(ans_a, ans_b, ans_c) < a)
            ans_a = a, ans_b = b, ans_c = c;
        else if (min3(ans_a, ans_b, ans_c) == a && ans_a + ans_b + ans_c < a + b + c)
            ans_a = a, ans_b = b, ans_c = c;
    }
    
    for (int b = 0; b <= n; b++) // b <= a, c
    {
        int a = b, c;
    
        while (((n - a * coeff_a - b * coeff_b) % coeff_c + coeff_c) % coeff_c != 0)
            a++;
        c = (n - a * coeff_a - b * coeff_b) / coeff_c;
    
        if (c < 0 || c < b)
            break; // 矛盾
    
        if (min3(ans_a, ans_b, ans_c) < b)
            ans_a = a, ans_b = b, ans_c = c;
        else if (min3(ans_a, ans_b, ans_c) == b && ans_a + ans_b + ans_c < a + b + c)
            ans_a = a, ans_b = b, ans_c = c;
    }
    
    for (int c = 0; c <= n; c++) // c <= a, b
    {
        int a = c, b;
    
        while (((n - a * coeff_a - c * coeff_c) % coeff_b + coeff_b) % coeff_b != 0)
            a++;
        b = (n - a * coeff_a - c * coeff_c) / coeff_b;
    
        if (b < 0 || b < c)
            break; // 矛盾
    
        if (min3(ans_a, ans_b, ans_c) < c)
            ans_a = a, ans_b = b, ans_c = c;
        else if (min3(ans_a, ans_b, ans_c) == c && ans_a + ans_b + ans_c < a + b + c)
            ans_a = a, ans_b = b, ans_c = c;
    }
    
    if (ans_a == -1)
        puts("-1");
    else
        printf("%d %d %d", ans_a, ans_b, ans_c);
    return 0;
}