题目描述
难度分:1800
输入T(≤1000)表示T组数据。所有数据的hi之和≤105。
每组数据输入n(1≤n≤50),x(1≤x≤108)表示有n个月,每个月的月底你会得到x元钱。
然后输入n行,每行两个数ci(0≤ci≤108)和hi(1≤hi≤1000),表示你可以在第i月的月初支付ci元钱,可以得到hi个单位的幸福。
注意第1月你没有钱。注意ci可以等于0,表示你可以免费获得hi的幸福。
输出你能得到的幸福总量的最大值。
输入样例
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
算法
动态规划
看到ci和x的取值范围,基本就确定这个状态不可能跟花费相关。
状态定义
f[i]表示当幸福值总量为i时,最低的花费。在这个定义下,如果i是可以达成的,那答案就是可以达成的i中最大的那一个。
状态转移
f[i]初始化为正无穷1012,表示都无解。边界就是f[0]=0,表示当没有幸福值时,就不需要任何代价。
一般情况下,我们就可以当背包来做了。外层循环遍历i∈[1,n],内层循环倒序遍历j∈[hi,m],其中m是所有hi的和。如果f[j−hi]+ci≤(i−1)x,说明前i−1个月的钱可以在幸福值为j−hi时花ci买hi的幸福值使得总幸福值变为j,这样就可以进行状态转移f[j]=f[j−hi]+ci,对于每个i,f[j]取最小值。
复杂度分析
时间复杂度
状态数量为O(m),单次转移的时间复杂度为O(n),所以整个算法的时间复杂度为O(nm)。
空间复杂度
空间消耗主要在于DP
数组f,它的空间上限是m=Σi∈[1,n]hi,即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;
}