算法
(贪心,DP) $O(TNM)$
本题关键点:
在某一种方案中,如果我们在第$i$天买入第$j$天卖出,其中 $i < j$,则等价于在第 $i$ 天买入,第 $i + 1$ 天卖出,第 $i + 1$ 天再买入, …, 在第 $j$ 天卖出。
因此任何一种方案都等价于只使用一种交易方式的方案,最优解也不例外:
- 交易方式:在某天买入,并在其相邻的后一天卖出。
因此我们只需考虑上面这一种交易方式即可。
此时所有交易不会跨越两天,因此我们的目标就变成了贪心策略:先尽可能使第二天的钱最多,再尽可能使第三天的钱最多,依次类推直到最后一天。
接下来的问题变成:
假设第 $i$ 天的钱数是 $m_i$,那么第 $i + 1$ 天的钱数最多是多少呢?
这是一个经典的完全背包问题:
- 背包容量是 $m_i$;
- 每个股票都是一种物品,体积是第 $i$ 天买入的价格,价值在第 $i$ 天买入第 $i + 1$ 天卖出的收益;
- 每天可以进行无限次交易,因此每种物品都是可以用无限次;
那么第 $i + 1$ 天的最大收益 $m_{i + 1}$ 就是 $m_i$ 加上背包模型所求出的最大收益。
本题时间复杂度恰好是 $10^8$,比较极限,因此可以加一些优化:
- 只有当某支股票的收益为正数时,才考虑使用该物品。
时间复杂度
一共有 $T \le 100$ 天,每天有 $N \le 100$ 支股票,每天的钱数最大是 $M \le 10000$。
算法中一共会算 $T - 1$ 次背包模型,每算一次的时间复杂度是 $O(NM)$,因此总时间复杂度是 $O(TNM) = 10^8$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 10010;
int t, n, m;
int f[M];
int w[N][N];
int main()
{
scanf("%d%d%d", &t, &n, &m);
for (int i = 1; i <= t; i ++ )
for (int j = 1; j <= n; j ++ )
scanf("%d", &w[i][j]);
for (int i = 1; i < t; i ++ )
{
memset(f, 0, sizeof f);
for (int j = 1; j <= n; j ++ )
if (w[i + 1][j] > w[i][j]) // 优化:只有在价值为正数时才会考虑使用该物品
for (int k = w[i][j]; k <= m; k ++ )
f[k] = max(f[k], f[k - w[i][j]] + w[i + 1][j] - w[i][j]);
m += f[m];
}
printf("%d\n", m);
return 0;
}
$Orz$
类似于邻项交换的贪心策略
循环最后为什么是 m+=f[m] 呢,这表示啥意思?是不是相当于,每一轮,我当下的M元进去完全背包,f[m]表示在m元时我现有的钱,然后下一天在开始的时候,我手里就是m+f[m]。 这一天,所有的f[] 都是0, 只要有差价,我就尝试是买,还是不买,此刻的最优解。如何理解f[k]是关键,就是我手里有k元,然后明天产生的收益。
# Orz
%%%%%%
666666
stO Orz
秒啊!
Orz
233333