2020ICPC南京 M.Monster Hunter

题目大意

一颗根为 \(1\) 的有 \((2≤≤2000)\) 个节点的树，每个节点有一个权值 \(ℎ_{} (1≤ℎ_{}≤10^9)\) ，能删除某个点的前提是其父亲节点已经被删除，并且删除一个节点的费用为 \(ℎ_{}+∑_{∈[]}ℎ_{}\) ，有 \(\) 次使用魔法的机会，每次使用可以免费并且无视限制条件地删去 \(1\) 个节点。分别求出当 \(=0\sim \) 时，删除全部节点所需要的最小花费。

思路

代码

#include<bits/stdc++.h>

#include<unordered_map>

#include<unordered_set>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> PII;

#define all(x) x.begin(),x.end()

#define int LL

//#define lc p*2+1

//#define rc p*2+2

#define endl '\n'

#define inf 0x3f3f3f3f

#define INF 0x3f3f3f3f3f3f3f3f

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#pragma warning(disable :4996)

const double eps = 1e-8;

const LL mod = 1000000007;

const LL MOD = 998244353;

const int maxn = 2010;

int T, N;

vector<int>G[maxn];

int vsize[maxn];

int hp[maxn], dp[maxn][maxn][2];

void add_edge(int from, int to)

{

	G[from].push_back(to);

}

void dfs(int v)

{

	vsize[v] = 1;

	dp[v][0][0] = hp[v], dp[v][1][1] = 0;

	for (int i = 0; i < G[v].size(); i++)

	{

		int to = G[v][i];

		dfs(to);

		for (int j = vsize[v]; j >= 0; j--)

		{

			for (int k = vsize[to]; k >= 1; k--)

			{

				if (j < vsize[v])

					dp[v][j + k][0] = min(dp[v][j + k][0], dp[v][j][0] + min(dp[to][k][0] + hp[to], dp[to][k][1]));

				if (j > 0)

					dp[v][j + k][1] = min(dp[v][j + k][1], dp[v][j][1] + min(dp[to][k][0], dp[to][k][1]));

			}

			dp[v][j][0] += min(dp[to][0][0] + hp[to], dp[to][0][1]);

			dp[v][j][1] += min(dp[to][0][0], dp[to][0][1]);

		}

		vsize[v] += vsize[to];

	}

}

void solve()

{

	dfs(1);

	for (int i = 0; i <= N; i++)

	{

		if (i < N)

			printf("%lld ", min(dp[1][i][0], dp[1][i][1]));

		else

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

	}

}

signed main()

{

	scanf("%lld", &T);

	while (T--)

	{

		//cnt = 0;

		scanf("%lld", &N);

		for (int i = 0; i <= N; i++)

		{

			for (int j = 0; j <= N; j++)

				dp[i][j][0] = dp[i][j][1] = INF;

		}

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

			G[i].clear();

		int fa;

		for (int i = 2; i <= N; i++)

		{

			scanf("%lld", &fa);

			add_edge(fa, i);

		}

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

			scanf("%lld", &hp[i]);

		solve();

	}

	return 0;

}

巴特西

2020ICPC南京 M.Monster Hunter

题目大意

思路

代码

最新文章

热门文章