「HNOI/AHOI2018」道路

传送门

Luogu

解题思路

考虑树形 \(\text{DP}\)

设状态 \(dp[u][i][j]\) 表示从首都走到点 \(u\) ，经过 \(i\) 条公路，\(j\) 条铁路的最小不方便值。

对于叶子节点也就是村庄，直接初始化，对于非叶子节点也就是城市，就从两个儿子向上转移。

而现在的一个问题就是：我们的 \(dp\) 数组根本开不下。

我们不得不优化空间。

考虑到一个性质：每次的答案都是从儿子向上合并，合并过后的节点就没用了。

所以我们只需要在dfs的过程中给每个节点记一个 \(dfn\)，满足：

\(dfn_{ls}=dfn_{fa} + 1, dfn_{rs}=dfn_{fa} + 2\)

我们把空间回收利用起来，很容易计算 \(dp\) 的第一位，只需要开到 \(2*40+1=81\) 即可。

这样就可以愉快的 DP 了，答案就是 \(dp[1][0][0]\)

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= c == '-', c = getchar();

	while (isdigit(c)) s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

typedef long long LL;

const int _ = 20010;

int n, a[_ << 1], b[_ << 1], c[_ << 1], ch[2][_];

LL dp[90][50][50];

inline void dfs(int s, int u, int x, int y) {

	if (u >= n) {

		for (rg int i = 0; i <= x; ++i)

			for (rg int j = 0; j <= y; ++j)

				dp[s][i][j] = 1ll * c[u] * (a[u] + i) * (b[u] + j);

		return;

	}

	dfs(s + 1, ch[0][u], x + 1, y);

	dfs(s + 2, ch[1][u], x, y + 1);

	int ls = s + 1, rs = s + 2;

	for (rg int i = 0; i <= x; ++i)

		for (rg int j = 0; j <= y; ++j)

			dp[s][i][j] = min(dp[ls][i + 1][j] + dp[rs][i][j], dp[ls][i][j] + dp[rs][i][j + 1]);

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n);

	for (rg int i = 1; i < n; ++i) {

		read(ch[0][i]), ch[0][i] = ch[0][i] < 0 ? n - ch[0][i] - 1 : ch[0][i];

		read(ch[1][i]), ch[1][i] = ch[1][i] < 0 ? n - ch[1][i] - 1 : ch[1][i];

	}

	for (rg int i = 1; i <= n; ++i)

		read(a[i + n - 1]), read(b[i + n - 1]), read(c[i + n - 1]);

	dfs(1, 1, 0, 0);

	printf("%lld\n", dp[1][0][0]);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「HNOI/AHOI2018」道路

解题思路

细节注意事项

参考代码

最新文章

热门文章