CF1249F Maximum Weight Subset(트리 DP or 욕심)

You are given a tree, which consists of n vertices. Recall that a tree is a connected undirected graph without cycles. Example of a tree. Vertices are numbered from 1 to n. All vertices have weights, the weight of the vertex v is av. Recall that the distance between two vertices in the tree is the number of edges on a simple path between them. Your task is to find the subset of vertices with the maximum total weight (the weight of the subset is the sum of weights of all vertices in it) such that there is no pair of vertices with the distance k or less between them in this subset.
Input The first line of the input contains two integers n and k (1≤n,k≤200) — the number of vertices in the tree and the distance restriction, respectively. The second line of the input contains n integers a1,a2,…,an (1≤ai≤105), where ai is the weight of the vertex i. The next n−1 lines contain edges of the tree. Edge i is denoted by two integers ui and vi — the labels of vertices it connects (1≤ui,vi≤n, ui≠vi). It is guaranteed that the given edges form a tree.
Output Print one integer — the maximum total weight of the subset in which all pairs of vertices have distance more than k.
Examples input 5 1 1 2 3 4 5 1 2 2 3 3 4 3 5 output 11 input 7 2 2 1 2 1 2 1 1 6 4 1 5 3 1 2 3 7 5 7 4 output 4
제목의 대의: 나무를 정하고 일부 노드를 선택해야 한다. 노드 두 개의 거리는 K보다 크고 각 노드는 권한이 있으며 총 권한이 가장 큰 점집을 구한다.

트리 DP

pp[i][j]는 노드 i를 뿌리로 하는 하위 트리가 j-1 깊이로 내려가는 노드를 취하지 않고 다른 노드가 임의로 있을 때 하위 트리의 최우선(최대 권한값)을 나타낸다.먼저 dp[i][j]로 i를 노드로 하는 하위 트리에서 얻은 노드의 가장 얕은 깊이가 j일 때의 최대치를 기록한 다음에 dp[i]의 접두사 최대치를 구하면 요구된 dp값을 얻을 수 있다.두 가지 상황으로 나뉜다. 만약에 j=0 dp [i] [0] = w e i g h t [i] + ∑d p [i s o n] [k] dp[i] [0] = weight[i] +\sum{}dp[ison][k]dp[i][0]=weight[i]+∑dp[ison][k]ison은 i노드의 아들을 나타낸다. 상기 방정식은 i노드를 취하고 i거리는 <=k의 노드를 취하지 않으며 다른 노드가 임의로 있을 때 가장 좋은 방법이다.만약 j가 0d p [i] [j] = dp[i] [j] = [j] = dp[i] [j] 0d p [i] [j] [j] [j] = dp[j] = dp[j] 1,k-3-j))otherison은 i의 아들 중 ison의 아들을 제외하면 max(j-1,k-j)는 가장 얕은 깊이를 반드시 j로 보장한다.마지막으로 접미사 최대치 구하는 거 잊지 마세요.

for(int j=k;j>=0;j--)dp[i][j]=max(dp[i][j],dp[i][j+1]);

이 dp 프로세스는 dfs로 실현할 수 있습니다.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#define lol long long
using namespace std;
lol read()
{
	lol x=0,y=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')y=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*y;
}
int n,k;
bool cont[205][205],b[205];
int weight[205],dp[205][205];
void dfs(int now)
{
	b[now]=true;
	int son[205];
	son[0]=0;
	for(int i=1;i<=n;i++)
	{
		if(cont[now][i]&&(!b[i]))dfs(i),son[++son[0]]=i;
	}
	//            
	b[now]=false;
	dp[now][0]=weight[now];
	for(int i=1;i<=son[0];i++)dp[now][0]+=dp[son[i]][k];
	//j=0    
	for(int i=1;i<=k;i++)
	{
		int tot=0;
		for(int j=1;j<=son[0];j++)
		{
			tot+=dp[son[j]][max(i-1,k-i)];
		}
		for(int j=1;j<=son[0];j++)
		{
			dp[now][i]=max(dp[now][i],dp[son[j]][i-1]+tot-dp[son[j]][max(i-1,k-i)]);
		}
	}
	//j   0    
	for(int i=k;i>=0;i--)dp[now][i]=max(dp[now][i],dp[now][i+1]);
	//     
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;i++)weight[i]=read();
	for(int i=1;i<n;i++)
	{
		int a=read(),b=read();
		cont[a][b]=cont[b][a]=true;
	
	dfs(1);
	printf("%d",dp[1][0]);
	return 0;
}

탐욕스러운 방법

하나의 노드를 취하고 ans+=의 값을 사용하면 우리는 <=k에서 떨어진 점의 값을 현재 노드의 값(자신을 포함)을 뺀 다음에 0보다 큰 노드를 찾아 반복적으로 조작한다. 이렇게 조작한 후에 우리는 노드 간의 충돌 여부를 고려할 필요가 없다. 예를 들어 a노드를 취한 후에 k거리 범위 내에서 b점을 얻었지만 이전의 조작으로 인해결과 등가ans+=max(weight[a],weight[b]).그러나 이 방법은 주의해야 한다. 방금 든 예에서 b노드를 취한 후에 b노드의 거리 k 이내의 노드를 현재의 b의 값을 빼고 사실은 a영역이 아니라 b영역의 노드를 a의 값으로 되돌려야 한다. 그러나 이렇게 하면 너무 번거롭다. 그래서 우리는 나무의 깊이가 가장 깊은 노드부터 조작을 시작한다. 깊이가 큰 노드는 반드시 깊이가 얕은 노드 앞에서 조작해야 한다. 그러면 그 번거로운 조작을 피할 수 있다.그 노드들이 a를 더하든 안 더하든 모두 마이너스이기 때문에 다음 조작에 영향을 주지 않기 때문에 알고리즘이 완성된 후 모든 점의 값은 반드시 마이너스이다.약간 돌려서 수동으로 시뮬레이션할 수 있어요.예를 들어 나는 나무 한 그루를 주었다. n개의 노드, 권한은 모두 1이고 2부터 n호의 노드는 모두 1의 아들이다. 1을 뿌리로 하고 k=1이다. 만약에 1부터 조작을 시작하면 한 번만 조작하면 모든 노드의 권한이 <=0,ans=1로 되어 분명히 틀렸다.2에서 n 노드를 먼저 처리하면 정답을 얻을 수 있다.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#define lol long long
using namespace std;
lol read()
{
	lol x=0,y=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')y=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*y;
}
int n,k;
bool cont[205][205],b[205];
int weight[205],ans,dis[205][205],deep[205],fs[205];
queue<int>q;
bool cmp(int a,int b){return deep[a]>deep[b];}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;i++)weight[i]=read();
	for(int i=1;i<n;i++)
	{
		int a=read(),b=read();
		cont[a][b]=cont[b][a]=true;
	}
	for(int i=1;i<=n;i++)
	{
		q.push(i);
		b[i]=true;
		while(!q.empty())
		{
			int now=q.front();
			q.pop();
			for(int j=1;j<=n;j++)
				if(cont[now][j]&&(!b[j]))dis[i][j]=dis[i][now]+1,q.push(j),b[j]=true;
		}
		memset(b,0,sizeof(b));
	}
	// n bfs            
	for(int i=1;i<=n;i++)deep[i]=dis[1][i],fs[i]=i;
	sort(fs+1,fs+n+1,cmp);
	//     
	for(int i=1;i<=n;i++)
	{
		int now=fs[i];
		if(weight[now]>0)
		{
			ans+=weight[now];
			for(int i=1;i<=n;i++)
				if(dis[now][i]<=k&&now!=i)weight[i]-=weight[now];
			weight[now]=0;
		}
	}
	//    
	printf("%d",ans);
	return 0;
}