[SDOI 2008] Sue的小球（提前算贡献的 DP） | 错题本

题目

[SDOI 2008] Sue的小球

分析

将之后的损失提前统计在 DP 的值中，就可以避免不知道时间无法计算损失的情况。然后区间 DP，$dp[l][r][0/1]$ 表示收集完 $[l,r]$ 的彩蛋（提前计算了对以后损失）最终停在 $l/r$（因为不可能吃完了还继续乱走）的最高分数，转移的时后从 $dp[l+1][r]$ 或者 $dp[l][r-1]$ 走过来，新增的时间是知道的，新增的损失就是新增的时间乘上还未收集的彩蛋的速度之和。

代码

#include <bits/stdc++.h>

int Read() {
	int x = 0; bool f = false; char c = getchar();
	while (c < '0' || c > '9')
		f |= c == '-', c = getchar();
	while (c >= '0' && c <= '9')
		x = x * 10 + (c ^ 48), c = getchar();
	return f ? -x : x;
}

typedef long long LL;

const int MAXN = 1000;

int N, X;
struct Point {
	LL x, y, v;
} E[MAXN + 5];
LL S[MAXN + 5];
LL Dp[MAXN + 5][MAXN + 5][2];

inline LL Sub(const int &lft, const int &rgt, const int &l, const int &r) {
	return (E[r].x - E[l].x) * (S[N] - (S[rgt] - S[lft - 1]));
}

int main() {
	N = Read(), X = Read();
	for (int i = 1; i <= N; i++)
		E[i].x = Read();
	for (int i = 1; i <= N; i++)
		E[i].y = Read();
	for (int i = 1; i <= N; i++)
		E[i].v = Read();
	E[++N].x = X;
	std::sort(E + 1, E + N + 1, [](const Point &i, const Point &j) {
		return i.x < j.x;
	});
	memset(Dp, -0x3f, sizeof Dp);
	for (int i = 1; i <= N; i++) {
		S[i] = S[i - 1] + E[i].v;
		if (E[i].x == X && !E[i].v && !E[i].y)
			Dp[i][i][0] = Dp[i][i][1] = 0;
	}
	for (int len = 2; len <= N; len++) {
		for (int lft = 1; lft + len - 1 <= N; lft++) {
			int rgt = lft + len - 1;
			Dp[lft][rgt][0] = std::max(Dp[lft + 1][rgt][1] - Sub(lft + 1, rgt, lft, rgt),
									   Dp[lft + 1][rgt][0] - Sub(lft + 1, rgt, lft, lft + 1));
			Dp[lft][rgt][1] = std::max(Dp[lft][rgt - 1][1] - Sub(lft, rgt - 1, rgt - 1, rgt),
									   Dp[lft][rgt - 1][0] - Sub(lft, rgt - 1, lft, rgt));
			Dp[lft][rgt][0] += E[lft].y;
			Dp[lft][rgt][1] += E[rgt].y;
		}
	}
	printf("%.3f", std::max(Dp[1][N][0], Dp[1][N][1]) / 1000.0);
	return 0;
}

本文地址：https://blog.csdn.net/C20190102/article/details/110174934