2* 사과나무 나무형 동태 기획
두 갈래 나무에 대해 뿌리 노드를 제외하고는 각 노드마다 상응하는 권한이 있다.이를 바탕으로 몇 개의 점을 보존하여 나무의 성질을 충족시키고 권한의 총계가 가장 크도록 해야 한다.
분석하다.
선건수.
ch[v,1],ch[v,2]는 각각 V 노드의 좌우 아이를 저장한다.dp[v, l]는 V를 뿌리로 하는 나무에 저장되어 L 노드의 최대 권한과 최대 권한을 보존합니다.Num[v]은 점 v의 권한입니다.
dp[v,l]=max{dp[ch[v,1],j]+dp[ch[v,2],l-j-1]+num[v]} (0<=j<=l-1)
여기에 특별히 지적한 바와 같이 그것을 여전히 두 갈래 나무로 만들기 위해 우리는 반드시 뿌리 노드를 보존해야 하기 때문에 j<=l-1.
그리고 가지를 줄일 수 있다.
그런 다음 2, 경계를 확인합니다.
만약 l=0이라면 dp[v,l]=0.
만약 v에 아이가 없다면 dp[v,l]=v의 권한값입니다.
그리고 3, 입력한 것은 m라인을 보존해야 하기 때문에 전환된 제목은 nm라인을 보존해야 하기 때문에 입력한 m라인은 1을 추가해야 한다.
코드
var
f:array[0..200,0..200] of longint;
a:array[0..200,1..3] of longint;
b:array[0..200,0..200] of longint;
v,num:array[0..200] of longint;
i,j,k,l:longint;
n,m:longint;
ans:longint;
procedure make(v:longint);
var
i,j,k:longint;
begin
for i:=1 to n do
begin
if b[v,i]>0 then
begin
a[v,1]:=i;
num[i]:=b[v,i]-1;
b[v,i]:=-1; b[i,v]:=-1;
make(i);
break;
end;
end;
for i:=1 to n do
begin
if b[v,i]>0 then
begin
a[v,2]:=i;
num[i]:=b[v,i]-1;
b[v,i]:=-1; b[i,v]:=-1;
make(i);
break;
end;
end;
end;
procedure dfs(r,l:longint);
var
i,j,k:longint;
begin
if f[r,l]<>0 then exit;
if l=0
then
begin
f[r,l]:=0;
exit;
end;
if (a[r,1]=0) and (a[r,2]=0)
then begin
f[r,l]:=num[r];
exit;
end;
for i:=0 to l-1 do
begin
dfs(a[r,1],i);
dfs(a[r,2],l-i-1);
if f[r,l]전재 대상:https://www.cnblogs.com/a-loud-name/p/6184826.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
