탐식하는 아홉 마리 용

나무 모양 dp를 자르기 시작합니다...
아이디어:
연구를 통해 m가 3보다 크면 m를 3으로 삼아 연산할 수 있다는 것을 발견하였다.
먼저 여러 갈래 나무를 두 갈래 나무로 전환시켜 각 노드의 아들과 형제를 찾기 편리하게 한다.
pp[i][j][k]: i 노드를 뿌리 노드로 하는 자수로 j개의 큰 머리가 있고 노드 i의 상태는 k이다. 이때의 괴로움치.(k=0,1) k=0일 때 작은 머리가 이 노드를 먹고 반대로 큰 머리가 먹는다.
map[i][j]: 노드 i에서 노드 j까지의 변장.
dp[x][j][1]=min(dp[x][j][1],dp[y][k][1]+tmp[j-k][1]+map[x][y],dp[y][k][0]+tmp[j-k][1]);
dp[x][j][0]=min(dp[x][j][0],dp[y][k][0]+tmp[j-k][0]+t               ,dp[y][k][1]+tmp[j-k][0]);
tmp[i][j]: 한 노드를 연산하기 전에 이미 연산한 노드가 형성한 dp[x][i][j];
t는 한 변의 양쪽이 모두 0일 때 반드시 증가해야 할 괴로움치를 대표한다.
 

#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

struct list

{

	int l;

	int r;

}node[1001];

int n,m,need;

int map[301][301];

int min3(int a,int b,int c)

{

	if(a>b)a=b;

	if(a>c)a=c;

	return a;

}

void init()

{

	int i,a,b,c;

	cin>>n>>m>>need;

	for(i=1;i<=n;i++)

	{

		node[i].l=node[i].r=0;

	}

	for(i=0;i<n-1;i++)

	{

		cin>>a>>b>>c;

		if(a>b)swap(a,b);

		map[a][b]=c;

		if(node[a].l==0)

		{

			node[a].l=b;

		}

		else

		{

			a=node[a].l;

			while(node[a].r)

			{

				a=node[a].r;

			}

			node[a].r=b;

		}

	}

}

int sum[301];

int dp[301][301][10];

int tmp[301][10];

void dfs(int x)

{

	dp[x][1][1]=0;

	dp[x][0][0]=0;

	int j,k;

	sum[x]=1;

	int i;

	i=node[x].l;

	while(i)

	{

		int y=i;

		dfs(y);

		int t;

		t=0;

		if(m==2)t=map[x][y];

		sum[x]+=sum[y];

		for(j=0;j<301;j++)

		{

			tmp[j][0]=dp[x][j][0];

			tmp[j][1]=dp[x][j][1];

		}

		memset(dp[x],0x2f,sizeof(dp[x]));

		for(j=sum[x];j>=0;j--)

		{

			for(k=j-1;k>=0;k--)dp[x][j][1]=min3(dp[x][j][1],dp[y][k][0]+tmp[j-k][1],dp[y][k][1]+tmp[j-k][1]+map[x][y]);

			for(k=j;k>=0;k--) dp[x][j][0]=min3(dp[x][j][0],dp[y][k][1]+tmp[j-k][0],dp[y][k][0]+tmp[j-k][0]+t);

		}

		i=node[i].r;

	}

}

int main()

{

	init();

	if(n<m+need-1)

	{

		printf("-1
");

		return 0;

	}

	memset(dp,0x2f,sizeof(dp));

	dfs(1);

	cout<<dp[1][need][1];

	return 0;

}