Luogu 题解 CF1107F Vasya and Endless Credits

本文主要是介绍Luogu 题解 CF1107F Vasya and Endless Credits，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

题意描述

给定 \(n\) 种贷款，第 \(i\) 种贷款可以让你立即收入 \(a_i\) 元，但接下来的 \(k_i\) 天内每天末尾你都要支出 \(b_i\) 元。你可以在任意时间购买贷款，每个贷款最多可购买一次，每天最多只能购买一个贷款。你手中的金钱可以为负。求在任意时间中你所拥有的金钱的最大值。

思路分析

设手中的钱在第 \(T\) 天达到最大值，贷款 \(i\) 购买的日期为第 \(T - x_i\) 天。

可以发现，在第 \(T\) 天，贷款可以分成三种类型：

• 1：不购买的贷款；
• 2：购买但未还清的贷款；
• 3：购买并且已经还清的贷款。

对于第1种贷款，无需考虑。

对于第2种贷款 \(i\)，其对答案的贡献 \(w_i=a_i - b_i \times x_i\)，显然，\(w_i\) 随 \(x_i\) 的减小而增大。因此，我们应使这些贷款尽可能晚一点购买，即应使 \(x_i\) 尽可能小。

对于第3种贷款 \(i\)，其对答案的贡献 \(w_i=a_i-b_i\times k_i\)，由于 \(w_i\) 与 \(x_i\) 无关，我们应该使这些贷款尽可能早点购买，即应使\(x_i\) 尽可能大，腾出位置在给第2种贷款以使答案最大化。

接下来考虑顺序问题：

对于所有的第2种贷款，其总收入与购买顺序无关，但其总支出会受其购买顺序影响。显然，我们应当尽可能地让 \(b\) 更大的贷款更晚地购买。在此不作证明，相信大家都能理解。而此时，由于购买顺序确定，我们便可以用 DP 来解决此问题。

具体做法

维护一个数组 \(dp_{i,j}\)，表示 \(i\) 号贷款在第 \(T-j\) 天购买时在第 \(T\) 天所能获得的最大金额。感性地理解：由于 \(T\) 不确定，于是我们将整个购买过程反过来，将 \(T\) 作为 \(0\)，将贷款“倒着”购买。

考虑如何维护：

• 1：若贷款 \(i\) 不购买，则 \(dp_{i,j}=dp_{{i-1},j}\)
• 2：若贷款 \(i\) 购买且未还清，则 \(dp_{i,j}=dp_{{i-1},{j-1}}+a_i-b_i\times (j-1)\)
• 3：若贷款 \(i\) 购买且已还清，则 \(dp_{i,j}=dp_{{i-1},j}+a_i-b_i\times k_i\)

重点解释一下第3种：对于购买且已经还清的贷款，我们将其尽可能往后放是为了让其不占用第2中贷款的位置。而取 \(dp_{{i-1},j}\) 而不是 \(dp_{{i-1},{j-1}}\) 本质上就是不让 \(i\) 占有位置，虽然与“尽早购买”不同，但是达到了一样的的目的。

特别地，若我们将贷款 \(i\) 放在最后面购买，即对于 \(dp_{{i},1}\)，在贷款 \(i\) 前面的贷款 \(p\)，若 \(a_p-b_p\times k_p>0\)，那么我们还是应该购买此贷款。可能我说的不是很清楚，用代码解释就是：

• \(dp_{i,0}=dp_{{i-1},0}+max(0,a_i-b_i\times k_i)\)

我相信你们都会懂的吧……

最后输出 \(\max(dp_{n,0},dp_{n,1},dp_{n,2},\cdots,dp_{n,n})\) 即可。

注意点

• 以 \(b\) 为关键字从大到小排序；
• DP 中的顺序与真实的购买顺序是相反的；
• 由于手中的金钱可以为负数，请将 \(dp\) 数组初始化为负无穷；
• 需要维护 \(dp_{i,0}\)；
• 记得开 long long。

AC代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N = 510;
ll dp[N][N];
struct Node
{
	ll a, b, k;
}f[N];
bool Sort(Node a, Node b)
{
	return a.b > b.b;
}
int main()
{
	ll ans = 0;
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> f[i].a >> f[i].b >> f[i].k;
		dp[0][i] = -0x7f;
	}
	sort(f + 1, f + 1 + n, Sort);
	for(int i = 1; i <= n; i ++)
	{
		ll w = 0;
		w = max(w, f[i].a - f[i].b * f[i].k);
		dp[i][0] = dp[i - 1][0] + w;
		for(ll p = 1; p <= n; p ++)
		{
			dp[i][p] = max(dp[i - 1][p] + w, dp[i - 1][p - 1] + f[i].a - f[i].b * (p - 1));
		}
	}
	for(int i = 0; i <= n; i ++) ans = max(ans, dp[n][i]);
	cout << ans << endl;

	return 0;
}

Written by \(\operatorname{Rosmarinus}\)

希望能对你有所帮助

这篇关于Luogu 题解 CF1107F Vasya and Endless Credits的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！