【洛谷P2016】战略游戏

题面

题解

树形\(dp\)（最大独立集）

设\(f_{i,0/1}\)表示\(dp\)到第\(i\)个点，在这个点放了（没放）士兵的最小花费

直接转移即可。

代码

#include<cstdio>

#include<cstring>

#include<vector>

#define RG register

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

#define clear(x, y) memset(x, y, sizeof(x));

namespace IO

{

	const int BUFSIZE = 1 << 20;

	char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;

	inline char getchar() { if (is == it) it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); return *is++; }

}

inline int read()

{

	int data = 0, w = 1;

	char ch = IO::getchar();

	while(ch != '-' && (ch < '0' || ch > '9')) ch = IO::getchar();

	if(ch == '-') w = -1, ch = IO::getchar();

	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = IO::getchar();

	return data*w;

}

const int maxn(2000);

int f[maxn][2], n;

std::vector<int> G[maxn];

typedef std::vector<int>::iterator iter;

void dfs(int x)

{

	f[x][1] = 1; f[x][0] = 0;

	for(RG iter it = G[x].begin(); it != G[x].end(); ++it)

		dfs(*it), f[x][1] += std::min(f[*it][1], f[*it][0]), f[x][0] += f[*it][1];

}

int main()

{

#ifndef ONLINE_JUDGE

	file(cpp);

#endif

	n = read();

	for(RG int i = 1, x, num; i <= n; i++)

	{

		x = read() + 1; num = read();

		for(RG int i = 1; i <= num; i++) G[x].push_back(read() + 1);

	}

	dfs(1); printf("%d\n", std::min(f[1][0], f[1][1]));

	return 0;

}

巴特西

【洛谷P2016】战略游戏

题面

题解

代码

最新文章

热门文章