欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-15 11:34:47
文章目录题目分析代码题目[SDOI 2008] Sue的小球分析将之后的损失提前统计在 DP 的值中,就可以避免不知道时间无法计算损失的情况。然后区间 DP,dp[l][r][0/1]dp[l][r][0/1]dp[l][r][0/1] 表示收集完 [l,r][l, r][l,r] 的彩蛋(提前计算了对以后损失)最终停在 l/rl / rl/r(因为不可能吃完了还继续乱走)的最高分数,转移的时后从 dp[l+1][r]dp[l + 1][r]dp[l+1][r] 或者 dp[l][r−1]dp[l]...

文章目录

题目

[SDOI 2008] Sue的小球

分析

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

代码

#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