luogu2014 选课背包类树形DP

题目大意：有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

对于每个节点u，定义u->DP[j]为在剩余课程数为j，以u为根的子树中能够获得的最高学分，则u->DP[j]=max{sum{v->DP[k] | sum[k]==j-1}|v∈u->Son}。

当u的子节点的子节点的DP值通过递归得出后，我们可以对u的每个DP[j]做一个背包。sum[k]==j-1提醒我们背包体积为j-1，k为物体的容量。DP求和提示我们DP[k]作为物体的价值。因为凑成j-1时每个v只选出一个v->DP[k]，这提示我们背包按照子节点进行分组，物体最多选一个。这便是一个分组背包！之后将u->DP[j]=u->DP[j-1]+u->score.

注意：

分组背包的初值设置不要忘，DP[0]=0,其余为负无穷。
枚举k时要倒序循环，因为要考虑到物品的体积可能为0，如果正序循环，0最后处理，此时的DP[j]已经是更改后的值。

DP[j]=DP[j-1]+score，而不是DP[j]=DP[j]+score

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cstdarg>

using namespace std;

const int MAX_NODE = 310, MAX_V = MAX_NODE;

int totV, totNode;

struct Node

{

	int DP[MAX_V];

	int Score;

	int Id;

	vector<Node*> Next;

}_nodes[MAX_NODE];

void AddEdge(int uId, int vId, int vScore)

{

	Node *u = uId + _nodes, *v = vId + _nodes;

	u->Id = uId;

	v->Id = vId;

	v->Score = vScore;

	u->Next.push_back(v);

}

void Dfs(Node *cur)

{

	memset(cur->DP, 0xcf, sizeof(cur->DP));

	cur->DP[0] = 0;

	int sonCnt = cur->Next.size();

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

		Dfs(cur->Next[i]);

	for (int son = 0; son < sonCnt; son++)

		for (int j = totV; j >= 0; j--)

			for (int k = j; k >= 0; k--)

				cur->DP[j] = max(cur->DP[j], cur->DP[j - k] + cur->Next[son]->DP[k]);

	if(cur!=_nodes)

		for (int j = totV; j > 0; j--)

			cur->DP[j] = cur->DP[j - 1] + cur->Score;

}

int Proceed()

{

	Node *root = _nodes;

	Dfs(root);

	return root->DP[totV];

}

int main()

{

#ifdef _DEBUG

	freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

	memset(_nodes, 0, sizeof(_nodes));

	int u, score;

	scanf("%d%d", &totNode, &totV);

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

	{

		scanf("%d%d", &u, &score);

		AddEdge(u, i, score);

	}

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

	return 0;

}

巴特西

luogu2014 选课背包类树形DP

最新文章

热门文章

巴特西

luogu2014 选课 背包类树形DP

最新文章

热门文章

luogu2014 选课背包类树形DP