bzoj1495 [NOI2006]网络收费复杂度分析+树上背包

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=1495

题解

通过观察可以发现，对于一个 \(lca\)，如果 \(nA \leq nB\)，那么就相当于是所有选 \(A\) 的都要付出 \(f[i][j]\) 的代价。这样我们可以轻松预处理出如果某个叶子在某个 \(LCA\) 处选择了比较少的那种付费方式时应该付出的代价和。

然后考虑 dp。令 \(dp[x][i]\) 为 \(x\) 为根的子树中，\(i\) 个叶子选择了第一种付费方式的最小总费用，然后可以通过背包合并来转移。

但是我们可以发现，每一个叶子的贡献取决于它的所有祖先的 \(nA\) 和 \(nB\) 的大小关系。这一点就不满足一般的 dp 的无后效性了。

然后我就没有办法了，开始自闭。

过了好久，拜读了一下题解，得知可以暴力枚举每一个非叶子的的情况，复杂度是可以保证的。

大概复杂度就是 \(T(m)=4T(\frac m2)+O(m^2)\)。根据主定理，\(m^2=m^{\log_2^4}=m^2\)，所以总时间复杂度为 \(m^2\log m = m^2n = n^{2n}n\)。

这个故事告诉我们时间复杂度的分析还是非常重要的，一个看起来很假的做法实际上可能是对的，要注意及时分辨算法的正确性，不要被表面的现象所迷惑。

代码如下：

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

#define lc x << 1

#define rc x << 1 | 1

const int N = 2048 + 7;

const int INF = 0x7f7f7f7f;

int n, m;

int a[N], c[N], f[N][N], w[N][N], col[N], dp[N][N];

inline void dfs(int x) {

	if (x >= m) {

		if (a[x - m + 1]) dp[x][0] = c[x - m + 1], dp[x][1] = 0;

		else dp[x][0] = 0, dp[x][1] = c[x - m + 1];

		for (int i = x >> 1; i; i >>= 1) dp[x][col[i] ^ 1] += w[x][i];

		return;

	}

	int siz = 1 << (n - std::__lg(x));

	memset(dp[x], 0x7f, sizeof(int) * (siz + 1));

	col[x] = 0, dfs(lc), dfs(rc);

	for (int i = 0; i <= (siz >> 1); ++i)

		for (int j = 0; i + j <= (siz >> 1); ++j)

			smin(dp[x][i + j], dp[lc][i] + dp[rc][j]);

	col[x] = 1, dfs(lc), dfs(rc);

	for (int i = 0; i <= (siz >> 1); ++i)

		for (int j = (siz >> 1) - i + 1; j <= (siz >> 1); ++j)

			smin(dp[x][i + j], dp[lc][i] + dp[rc][j]);

}

inline void ycl() {

	for (int i = 1; i <= m; ++i) {

		for (int j = i + 1; j <= m; ++j) {

			int x = i + m - 1, y = j + m - 1, lca = x >> (std::__lg(x ^ y) + 1);

			w[x][lca] += f[i][j], w[y][lca] += f[i][j];

		}

	}

}

inline void work() {

	ycl();

	dfs(1);

	int ans = INF;

	for (int i = 0; i <= m; ++i) smin(ans, dp[1][i]);

	printf("%d\n", ans);

}

inline void init() {

	read(n), m = 1 << n;

	for (int i = 1; i <= m; ++i) read(a[i]);

	for (int i = 1; i <= m; ++i) read(c[i]);

	for (int i = 1; i <= m; ++i)

		for (int j = i + 1; j <= m; ++j)

			read(f[i][j]), f[j][i] = f[i][j];

}

int main() {

#ifdef hzhkk

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

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj1495 [NOI2006]网络收费复杂度分析+树上背包

题目传送门

题解

最新文章

热门文章

巴特西

bzoj1495 [NOI2006]网络收费 复杂度分析+树上背包

题目传送门

题解

最新文章

热门文章

bzoj1495 [NOI2006]网络收费复杂度分析+树上背包