Solution

用传统的思想考虑正推，发现后面的答案依赖于当前的 \(p\)，你不但要记录前 \(i\) 个还要记录 \(p\)，显然空间爆炸。

类似 AcWing 300. 任务安排1，不妨考虑每次操作对后面整体的影响：

如果你采矿，之后的所有操作代价都会变为原来的 \(1 - 0.01k\)。（因为所有操作代价都是 \(p\) 的乘积，并且你改变了 \(p\)）。
如果你维修，之后所有操作代价都会变为原来的 \(1 + 0.01c\)。

不妨初始假设在每个位置时，\(p\) 都还是初始的 \(w\)，很明显从后向前推，不再具有后效性。

状态定义

设 \(f_i\) 表示 \(i\) ~ \(n\) 的最大收入。

状态转移

什么也不做 \(f_i \gets f_{i + 1}\)
如果这个星球是资源型，可以开采，代价变换：\(f_i \gets w · a_i + (1 - 0.01k)f_{i+1}\)
如果这个星球是维修型，类似的：\(f_i \gets - w·b_i + (1 + 0.01c)f_{i+1}\)

Code

#include <iostream>

#include <cstdio>

using namespace std;

const int N = 100005;

int n, K, C, W, t[N], v[N];

double f[N];

int main() {

	scanf("%d%d%d%d", &n, &K, &C, &W);

	for (int i = 1; i <= n; i++) scanf("%d%d", t + i, v + i);

	for (int i = n; i; i--) {

		if (t[i] == 1) f[i] = max(f[i + 1], v[i] * W + (1 - 0.01 * K) * f[i + 1]);

		else f[i] = max(f[i + 1], -v[i] * W + (1 + 0.01 * C) * f[i + 1]);

	}

	printf("%.2lf\n", f[1]);

	return 0;

}

巴特西

落谷 P1412 经营与开发

Solution

状态定义

状态转移

Code

最新文章

热门文章