[낙곡] P2015 두 갈래 사과나무(#나무형dp)
2158 단어 로곡 오리지널동적 기획동적 계획 -- 트리 dp
사과나무 한 그루가 있는데 나뭇가지가 갈라지면 틀림없이 두 갈래로 갈라진다.
이 나무는 모두 N개의 결점(잎점 또는 나뭇가지의 갈라진 점)이 있는데 번호는 1-N이고 나무 뿌리의 번호는 반드시 1이다.
우리는 나뭇가지 양쪽이 연결된 결점의 번호로 나뭇가지의 위치를 묘사한다.아래는 네 개의 나뭇가지가 있는 나무이다
2 5
\ /
3 4
\ /
1
지금 이 나무는 가지가 너무 많아서 가지를 잘라야 한다.그러나 일부 나뭇가지에는 사과가 자란다.
보존해야 할 나뭇가지의 수를 정해 최대 얼마의 사과를 남길 수 있는지 구해라.
입력 형식
1행 2개, N 및 Q(1<=Q<=N, 1
N은 나무의 결점 수를 나타내고 Q는 보존할 나뭇가지의 수를 나타낸다.다음 N-1 줄은 나뭇가지에 대한 정보를 설명합니다.
줄마다 3개의 정수가 있는데, 앞의 두 개는 연결된 결점의 번호이다.세 번째 수는 이 나뭇가지에 있는 사과의 수량이다.
나뭇가지마다 사과가 3만 개를 넘지 않는다.
출력 형식
한 개수, 가장 많이 남길 수 있는 사과의 수.
출력 샘플 가져오기
#1 복사 입력
5 2
1 3 1
1 4 10
2 3 20
3 5 20
출력 #1 복사
21사고의 방향
수강신청이랑 비슷하네.
뿌리 노드에서 m개의 가장자리를 찾아 마지막에 얻은 사과가 가장 많고 마지막에 얻은 것은 온전한 나무이다.
본 문제를 보기 전에 P2014 수강신청을 먼저 보는 것을 권장합니다.
dp[i][j]를 노드 i의 자수에 j개의 가장자리를 보존하고 가장 많이 보존할 수 있는 사과 수를 유지한다.분명히 노드 i의 하위 나무에 가장자리를 보존하는 것은 노드 i와 관계가 없다.수강신청 문제에서 노드 i가 그의 자수에서 j과목을 선택하는 것은 자신을 포함하는 것이다. 왜냐하면 i는 먼저 수강하기 때문이다.
그래서 방정식회와 수강신청은 약간 다르다.
dp[i][j]=max(dp[i][j],dp[i][j-k-1]+dp[son][k])
답은 dp[1][m]이다.
#include
#include
using namespace std;
int n,m,s,head[1001],cnt,dp[1001][1001],value[1001][1001];
bool vis[1001];// vis
struct node
{
int nxt,to,value;
}e[2001];
inline void add(int u,int v,int val)
{
e[++cnt].to=v;
e[cnt].nxt=head[u];
e[cnt].value=val;
head[u]=cnt;
}
void dfs(int i,int fa)
{
register int u,j,k;
for(u=head[i];u;u=e[u].nxt)
{
int v(e[u].to);
if(fa==v) continue;// ， （ ）
dfs(v,i);
for(j=m;j>=1;j--)
{
for(k=0;k<=j-1;k++)
{
dp[i][j]=max(dp[i][j],dp[i][j-k-1]+dp[v][k]+value[i][v]);
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
register int i,j;
cin>>n>>m;
for(i=1;i<=n-1;i++)
{
int u,v,val;
cin>>u>>v>>val;//
value[u][v]=val;// ， ，
value[v][u]=val;
add(u,v,val);
add(v,u,val);
}
dfs(1,-1);
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[낙곡] P2285 [HNOI2004] 두더지 잡기(#선형 dp)n*n의 격자에서 어떤 순간에 두더지는 특정한 격자에서 머리를 내밀어 바람을 쐬곤 한다.너는 로봇을 제어해서 두더지를 잡을 수 있다. 만약 i시간에 두더지가 어떤 격자에 나타나고 로봇도 같은 격자에 있으면 이 두더지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
