P5468 [NOI2019]回家路线

NOI2019D1T1

NOI中的送分题难度?

俗话说得好,一日不更博,一日不吃饭

然后吃完一天饭的我来更博了/kk

题目大意：

现在有n个城市，城市之间有m条火车可以到达。

第i条火车是从第 $x_ix$ 出发并到达 $y_i$ ，是在 $p_i$ 时间出发，并在 $q_i$ 时间到达。

火车只能够在前一辆到达后才能乘坐。

设共乘坐了k辆火车，那么他的代价是 $(q_{s_{k}}+\left(A \times p_{s_{1}}^{2}+B \times p_{s_{1}}+C\right)+\sum_{j=1}^{k-1}\left(A\left(p_{s j+1}-q_{s_{j}}\right)^{2}+B\left(p_{s_{j+1}}-q_{s_{j}}\right)+C\right)$

求最小代价。

这个上去第一眼就能想到DP吧,dp[i][j]表示i时刻在j的最小时间花费,考虑转移时如果这个时候有车就用车转移一下,否则就等待,从dp[k][j]转移过来,随意算下等待代价就好

然后这个东西显然复杂度还挺不行,怎么都是个 $O(nt^2)$ ,想办法优化一个转移?

你会发现一个基本的决策单调性,也就是说如果时刻 $l<k<i<j$ 满足了k对于i更优,那么对于i之后的j,j到l的代价只会比j到k的更大,所以一定不会再次启用决策l

这样就可以决策单调性干掉一个t,O(nt)了

这个做法可以通过本题,不过还不是最优秀的

考虑再优化,因为我们坐车决策一共m个,所以只要把m个打出来按照某某个方式排序DP就好

咋排序?当然是按照时间啦!出发时间越小坑定越靠前啦,所以这样排序之后 $f[i]$ 表示考虑到第i个决策,第i个必选,目前人处在 $y_i$ ,所花最小时间

转移O(m)枚举之前一个 $y_j==x_i$ ,然后算一下等的代价进行转移

dp[i]= \min_{j<i,y_j==x_i,q[j]<p[i]}(dp[j]+A(p_i-q_j)^2+B(p_i-q_j)+C)

dp[i]=dp[j]+(Ap_i^2)+(Aq_j^2)-2Ap_iq_j+Bq_j+Bp_i+C

你会发现 $p_i$ 有单调性,而且 $-2Aq_j$ 也有单调性,分别x,k

所以y,b是啥就不用了我说了吧

时间复杂度仅有O(m)

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 2e5 + 7;
#define ll long long
#define db double

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
#undef BUF_SIZE
}
using namespace fastIO;


inline int ymax(register int a, register int b) {
	return a > b ? a : b;
}

inline ll ymin(register ll a, register ll b) {
	return a < b ? a : b;
}

struct node {
	ll x, y;

	int id;
};

int n, m, A, B, C, maxT = 0;

int x[MAXN], y[MAXN], p[MAXN], q[MAXN], home[MAXN];
ll ans = 0x3f3f3f3f3f3f3f, dp[MAXN];
vector<int> d[1005];
vector<node> que[MAXN];
queue<int> res[1005];


inline db gslope(register node a, register node b) {
	return 1.0 * (a.y - b.y) / (1.0 * (a.x - b.x));
}

inline void ins(register int id) {
	int pos = y[id];
	node now = (node) {
		q[id], dp[id] + A *q[id]*q[id] - B *q[id], id
	};
	while(que[pos].size() - home[pos] >= 2) {
		int len = que[pos].size();

		if(gslope(que[pos][len - 1], que[pos][len - 2]) <
				gslope(que[pos][len - 2], now))
			break;
		que[pos].pop_back();
		// printf("%d %d\n", len, home[pos]);
	}
	que[pos].push_back(now);
}

inline void del(register db slpe, register int pos) {
	while(que[pos].size() - home[pos] >= 2) {
		// printf("%lf %d?! ", gslope(que[pos][home[pos]], que[pos][home[pos] + 1]), home[pos]);

		if(gslope(que[pos][home[pos]], que[pos][home[pos] + 1]) >
				slpe)
			return ;
		++home[pos];
	}
	// puts("");
}


int main() {
	// freopen("test.in", "r", stdin);
	n = read();
	m = read();
	A = read();
	B = read();
	C = read();
	for(register int i = 1; i <= m; ++i) {
		x[i] = read();
		y[i] = read();
		p[i] = read();
		q[i] = read();
		// printf("%d %d %d %d\n", x[i], y[i], p[i], q[i]);
		maxT = ymax(maxT, q[i]);
	}
	for(register int i = 1; i <= m; ++i) {
		d[p[i]].push_back(i);
	}
	que[1].push_back((node) {
		0, 0, 0
	});
	for(register int t = 0; t <= maxT; ++t) {
		while(!res[t].empty()) {
			ins(res[t].front());
			res[t].pop();
		}
		int len = d[t].size();
		// printf("%d %d\n", t, d[t].size());
		for(register int k = 0; k < len; ++k) {
			int id = d[t][k];
			int pos = x[id];
			// printf("%d %d ", id, pos);
			if(que[pos].size() == home[pos]) {
				continue;
			}
			db slpe = 2.0 * A * p[id];
			// printf("%lf? ", slpe);

			del(slpe, pos);
			int j = que[pos][home[pos]].id;
			// printf("%d!! \n", j);

			dp[id] = dp[j] + 1ll * A * (p[id] - q[j]) * (p[id] - q[j]) + 1ll * B * (p[id] - q[j]) + C;
			// /printf("%d *\n", dp[id]);

			res[q[id]].push(id);
			if(y[id] == n)
				ans = ymin(ans, dp[id] + q[id]);

		}
	}
	printf("%d\n", ans);
	return 0;
}

夏晓光(loveJY)的博客

P5473 [NOI2019]I 君的探险