题目描述

难度分:$1800$

输入$T(\leq 1000)$表示$T$组数据。所有数据的$h_i$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 50)$，$x(1 \leq x \leq 10^8)$表示有$n$个月，每个月的月底你会得到$x$元钱。

然后输入$n$行，每行两个数$c_i(0 \leq c_i \leq 10^8)$和$h_i(1 \leq h_i \leq 1000)$，表示你可以在第$i$月的月初支付$c_i$元钱，可以得到$h_i$个单位的幸福。

注意第$1$月你没有钱。注意$c_i$可以等于$0$，表示你可以免费获得$h_i$的幸福。

输出你能得到的幸福总量的最大值。

输入样例

7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2

输出样例

0
10
200
15
1
9
9

算法

动态规划

看到$c_i$和$x$的取值范围，基本就确定这个状态不可能跟花费相关。

状态定义

$f[i]$表示当幸福值总量为$i$时，最低的花费。在这个定义下，如果$i$是可以达成的，那答案就是可以达成的$i$中最大的那一个。

状态转移

$f[i]$初始化为正无穷$10^{12}$，表示都无解。边界就是$f[0]=0$，表示当没有幸福值时，就不需要任何代价。

一般情况下，我们就可以当背包来做了。外层循环遍历$i \in [1,n]$，内层循环倒序遍历$j \in [h_i,m]$，其中$m$是所有$h_i$的和。如果$f[j-h_i]+c_i \leq (i-1)x$，说明前$i-1$个月的钱可以在幸福值为$j-h_i$时花$c_i$买$h_i$的幸福值使得总幸福值变为$j$，这样就可以进行状态转移$f[j]=f[j-h_i]+c_i$，对于每个$i$，$f[j]$取最小值。

复杂度分析

时间复杂度

状态数量为$O(m)$，单次转移的时间复杂度为$O(n)$，所以整个算法的时间复杂度为$O(nm)$。

空间复杂度

空间消耗主要在于DP数组$f$，它的空间上限是$m=\Sigma_{i \in [1,n]}h_i$，即$O(m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 51;
const LL INF = 1e12;
int T, n, x, c[N], h[N];
LL f[100001];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &x);
        int tot = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &c[i], &h[i]);
            tot += h[i];
        }
        for(int i = 1; i <= tot; i++) {
            f[i] = INF;
        }
        f[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = tot; j >= h[i]; j--) {
                if(f[j - h[i]] + c[i] <= (i - 1LL)*x) {
                    f[j] = min(f[j], f[j - h[i]] + c[i]);
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= tot; i++) {
            if(f[i] < INF) {
                ans = i;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}