题目描述

难度分:$2600$

输入$n(1 \leq n \leq 500)$和$n$个三元组$(a_i,b_i,k_i)$，元素范围$[1,10^9]$。

银行提供$n$个贷款业务。

第$i$个贷款，可以贷到$a_i$元钱，分期$k_i$个月，每月底还$b_i$元钱（从办理贷款当月开始还）。

只能在月初办理贷款，且每月只能办理一个贷款。同一个贷款不能重复办理。

张三想在未来某个月的中旬买一辆车，买车的钱全部来自贷款。输出这辆车的最高价格。

注：张三并不在乎买车后要还银行多少钱。他只是开着车出了国，这样银行就再也找不到他了。

输入样例$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 \times k > 0$，那么直接白嫖$a - b \times k$元钱。注意这只是一个可选项，这样的贷款也可以使用下面的贪心策略二。

贪心策略二：假设我们最终办理了$m$个贷款，那么这$m$个贷款的办理顺序按照$b$从小到大排序，依次办理（每月办理一个）是最优的。特别地，最后办理的贷款，办理完就直接跑路，白嫖$a$元钱。

为了方便计算，按照$b$从大到小排序，也就是把最后办理的贷款排在左边。

问题相当于给你两个序列：

$A = [0,1,2,…]$，表示需要还钱的月份数。
$B = [(a_0,b_0,k_0),(a_1,b_1,k_1),(a_2,b_2,k_2),…]$，表示按照$b$从大到小排序后的贷款列表。

我们要从$B$中选一个子序列，和$A$的前缀匹配。最左边的贷款可以得到$a_0$元钱（办理完就跑路），其次的贷款可以得到$a_1-b_1$元钱，依此类推，第$j$个贷款可以得到$a_1-b_1 \times (j-1)$元钱。

状态定义

定义$f(i,j)$表示从前$i$个贷款中选一个长为$j$的子序列，与上文$A$数组的前缀匹配，所得到的最大收益。在这个定义下，最终的答案就是：$f(n-1,0)$,$f(n-1,1)$,$f(n-1,2)$, …,$f(n-1,n)$中的最大值。

状态转移

分类讨论：

1. 不选$B[i]$，那么$f(i,j) = f(i-1,j)$。
2. 选$B[i]$，但直接白嫖（贪心策略一），$f(i,j)=f(i-1,j) + max(a-b \times k,0)$。注意$j$是不变的，因为完全可以把这个贷款独立出来办理，躺赚$max(a-b \times k,0)$元钱。
3. 选$B[i]$，且$j-1$个月之后就跑路（贪心策略二），$f(i,j) = f(i-1,j-1) + a-b \times (j-1)$。注意只有在$j \gt 0$时才能转移。

以上三者取最大值进行转移，用记忆化搜索来实现这个DP。

$base$ $case$：$f(-1,j) = 0$。

复杂度分析

时间复杂度

需要枚举$j \in [0,n]$依次进行动态规划，预留足够的空间重复使用同一个DP矩阵，状态数量为$O(n^2)$级别，一共$O(n)$次DP。单次转移是$O(1)$的，因此整个算法的时间复杂度为$O(n^3)$。

空间复杂度

除了输入的三元组数组$(a,b,k)$，空间消耗主要在于DP矩阵。因此，整个算法的额外空间复杂度为$O(n^2)$。

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;
}