题目描述
难度分:2600
输入n(1≤n≤500)和n个三元组(ai,bi,ki),元素范围[1,109]。
银行提供n个贷款业务。
第i个贷款,可以贷到ai元钱,分期ki个月,每月底还bi元钱(从办理贷款当月开始还)。
只能在月初办理贷款,且每月只能办理一个贷款。同一个贷款不能重复办理。
张三想在未来某个月的中旬买一辆车,买车的钱全部来自贷款。输出这辆车的最高价格。
注:张三并不在乎买车后要还银行多少钱。他只是开着车出了国,这样银行就再也找不到他了。
输入样例1
4
10 9 2
20 33 1
30 115 1
5 3 2
输出样例1
32
输入样例2
3
40 1 2
1000 1100 5
300 2 1
输出样例2
1337
算法
贪心+动态规划
又是不会做周五茶的一周,听说这题可以用费用流或者KM算法做,不会。这里只能学习贪心+DP
的做法了。
有两个贪心的想法:
贪心策略一:如果某个贷款的a−b×k>0,那么直接白嫖a−b×k元钱。注意这只是一个可选项,这样的贷款也可以使用下面的贪心策略二。
贪心策略二:假设我们最终办理了m个贷款,那么这m个贷款的办理顺序按照b从小到大排序,依次办理(每月办理一个)是最优的。特别地,最后办理的贷款,办理完就直接跑路,白嫖a元钱。
为了方便计算,按照b从大到小排序,也就是把最后办理的贷款排在左边。
问题相当于给你两个序列:
A=[0,1,2,…],表示需要还钱的月份数。
B=[(a0,b0,k0),(a1,b1,k1),(a2,b2,k2),…],表示按照b从大到小排序后的贷款列表。
我们要从B中选一个子序列,和A的前缀匹配。最左边的贷款可以得到a0元钱(办理完就跑路),其次的贷款可以得到a1−b1元钱,依此类推,第j个贷款可以得到a1−b1×(j−1)元钱。
状态定义
定义f(i,j)表示从前i个贷款中选一个长为j的子序列,与上文A数组的前缀匹配,所得到的最大收益。在这个定义下,最终的答案就是:f(n−1,0),f(n−1,1),f(n−1,2), …,f(n−1,n)中的最大值。
状态转移
分类讨论:
- 不选B[i],那么f(i,j)=f(i−1,j)。
- 选B[i],但直接白嫖(贪心策略一),f(i,j)=f(i−1,j)+max(a−b×k,0)。注意j是不变的,因为完全可以把这个贷款独立出来办理,躺赚max(a−b×k,0)元钱。
- 选B[i],且j−1个月之后就跑路(贪心策略二),f(i,j)=f(i−1,j−1)+a−b×(j−1)。注意只有在j>0时才能转移。
以上三者取最大值进行转移,用记忆化搜索来实现这个DP
。
base case:f(−1,j)=0。
复杂度分析
时间复杂度
需要枚举j∈[0,n]依次进行动态规划,预留足够的空间重复使用同一个DP
矩阵,状态数量为O(n2)级别,一共O(n)次DP
。单次转移是O(1)的,因此整个算法的时间复杂度为O(n3)。
空间复杂度
除了输入的三元组数组(a,b,k),空间消耗主要在于DP
矩阵。因此,整个算法的额外空间复杂度为O(n2)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510;
LL memo[N][N];
struct Offer {
int a, b, k;
bool operator<(const Offer other) const {
return b > other.b;
}
} offers[N];
LL dfs(int i, int j) {
if(i < 0) return 0;
LL &v = memo[i][j];
if(v != -1) return v;
Offer t = offers[i];
LL res = dfs(i - 1, j) + max(t.a - (LL)t.b * t.k, 0LL);
if(j > 0) {
res = max(res, dfs(i - 1, j - 1) + t.a - t.b * (j - 1LL));
}
return v = res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> offers[i].a >> offers[i].b >> offers[i].k;
}
sort(offers, offers + n);
memset(memo, -1, sizeof memo);
LL ans = 0;
for(int j = 0; j <= n; j++) {
ans = max(ans, dfs(n - 1, j));
}
cout << ans << endl;
return 0;
}