题目链接：传送门

Description

大赛将至，摆在你面前的是n道题目，第 i(1≤i≤n) 道题目能提升 ai 点智力值，代码量为 bi KB，无聊值为 ci ，求至少提升m点智力值的情况下，所做题目代码量之和 ∗ 无聊值之和最小为多少

Solution

这道题用到了求最小乘积生成树的思想 只是把求最小乘积生成树时的Kruskal换成Dp即可 Dp方程：

TeX parse error: Undefined control sequence \[

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 1000 + 10;

struct edge
{
    int a, b, c, v;
}A[Maxn];

struct point
{
    int x, y;
    bool operator < (const point &a) const
    {
        unsigned int p = x; p *= y;
        unsigned int q = a.x; q *= a.y;
        return q == p ? x < a.x : p < q;
    }
};

point Ans;

int N, M, MAX;
int Dp[1000 + 10];

point save[1000 + 10];

inline point DP ()
{
    point now;
    now.x = now.y = 1e9;
    //  cout<<now.x<<" "<<now.y<<endl;
    for (int i = 1; i <= MAX; ++i) Dp[i] = 0x3f3f3f3f3f3f3f3f;
    Dp[0] = 0;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = MAX; j >= A[i].v; --j)
        {
            if (Dp[j] > Dp[j - A[i].v] + A[i].c)
            {
                Dp[j] = Dp[j - A[i].v] + A[i].c;
                save[j].x = save[j - A[i].v].x + A[i].a;
                save[j].y = save[j - A[i].v].y + A[i].b;
            }
        }
    }
    int k = M;
    for (int i = M; i <= MAX; ++i) if (Dp[k] > Dp[i]) k = i;
    now = save[k];
    if (now < Ans) Ans = now;
    return now;
}

inline int mul (point a, point b, point c)
{
    return (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y);
}

inline void Solve (point a, point b)
{
    for (int i = 1; i <= M; ++i)
        A[i].c = A[i].b * (a.x - b.x) + A[i].a * (b.y - a.y);
    point c = DP();
    if (mul(a, b, c) <= 0) return ;
    Solve (a, c);
    Solve (c, b);
}

inline void Init ()
{
    Ans.x = Ans.y = 1e9;
    MAX = 0;
    memset(save, 0, sizeof save);
}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%lld%lld", &N, &M))
    {
        Init();
        for (int i = 1; i <= N; ++i)
            scanf("%lld%lld%lld", &A[i].v, &A[i].a, &A[i].b), MAX += A[i].v;
        for (int i = 1; i <= N; ++i) A[i].c = A[i].a;
        point a = DP();
        for (int i = 1; i <= N; ++i) A[i].c = A[i].b;
        point b = DP();
        Solve (b, a);
        printf("%lld\n", Ans.x * Ans.y);
    }
    return 0;
}