GDSOI 2008 생선 폭탄
1942 단어 DP
// DP
uses math;
type tre=record
left,right,fa:longint;
end;
var t:array[0..100000]of tre;
tree:array[1..100000,0..2]of longint;
h,c,stack:array[1..100000]of longint;
d:array[0..100000,0..5]of int64;
root,n,k:longint;
procedure writel;
var i,j:longint;
ans:int64;
begin
ans:=high(int64);
for i:=0 to k do
ans:=min(ans,d[root,i]);
writeln(ans);
end;
procedure DP(x:longint);
var i,j,j1,j2,l:longint;
begin
if x=0 then exit;
DP(t[x].left);
DP(t[x].right);
for i:=0 to k do
for j:=0 to k-i do
begin
d[x,i+j]:=min(max(d[t[x].left,i],d[t[x].right,j])+c[x],d[x,i+j]);
if i+j+1<=k then
d[x,i+j+1]:=min(max(d[t[x].left,i],d[t[x].right,j]),d[x,i+j+1]);
end;
end;
procedure maketree;
var i,j,top,tot:longint;
begin
top:=0;
for i:=1 to n do
begin
{t[i].st:=h[i];
if top<>0 then
begin
tot:=top;
top:=i;
while (h[i]>t[tot].st)and(t[tot].fa<>0) do
tot:=t[tot].fa;
if h[i]>t[tot].st then
t[tot].fa:=i;
if (t[tot].fa<>0)and(tot<>top) then
begin
t[i].fa:=t[tot].fa;
t[tot].fa:=i;
end;
if (t[tot].fa<>0)and(tot=top) then
t[i].fa:=tot;
end
else
top:=1;}
j:=Top;
while (j>0)and(h[Stack[j]]Top then
t[Stack[j+1]].fa:=i;
if j<>0 then
t[i].fa:=Stack[j];
Top:=j+1;
Stack[Top]:=i;
end;
for i:=1 to n do
if t[i].fa=0 then
root:=i
else
begin
inc(tree[t[i].fa,0]);
tree[t[i].fa,tree[t[i].fa,0]]:=i;
end;
for i:=1 to n do
begin
t[i].left:=tree[i,1];
t[i].right:=tree[i,2];
end;
end;
procedure init;
var i,j:longint;
begin
readln(n,k);
for i:=1 to n do
readln(h[i],c[i]);
end;
begin
init;
maketree;
fillchar(d,sizeof(d),127);
d[0,0]:=0;
DP(root);
writel;
end.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.