- Rx,y = 0 với (x = 0 hoặc y = 0)
- Rx,y = Rx-1,y-1 – Rx,y-1 – Rx-1,y + Ax,y
Như vậy ta có thể tính số hoa nằm trong
khoảng hình chữ nhật với ô trái dưới là (x1,
y1), ô phải trên là (x2, y2) trong O(1) theo công thức:
Rx2,y2 – Rx2,y1-1 – Rx1-1,y2 + Rx1-1,y1-1
Để qua được 50% số test, bạn chỉ
cần duyệt các cạnh của 2 hình chữ nhật
(độ phức tạp là O(w4l4). Nhưng để qua
được hết tất cả các test, bạn cần
phải có một thuật toán tốt hơn như sau:
Ta có nhận xét là 2 hình chữ nhật không giao nhau thì
sẽ tồn tại ít nhất một đường
thẳng (ngang hoặc dọc) chia mảnh vườn thành
2 phần trong đó mỗi phần có một hình chữ
nhật được chọn.
Như vậy, ta sẽ duyệt mọi hình chữ nhật
thỏa mãn trong đó có k cây hoa. Nhưng với thuật
toán duyệt O(w2l2) sẽ không đáp
ứng được thời gian, vì vậy ta có một
cách duyệt tốt hơn như sau:
Duyệt 2 cạnh trên (y2) và dưới (y1) của hình
chữ nhật. Chúng ta sẽ xét các hình chữ nhật có 2
cạnh như thỏa mãn điều kiện đó.
Với những hình chữ nhật có cạnh trái x1,
cạnh phải x2 ta sẽ xét các trường hợp sau:
- Nếu số lượng hoa = k thì ghi nhận hình chữ
nhật (x1, y1, x2, y2)
- Nếu số lượng hoa < k thi` ta(ng
x2.
- Nếu số lượng hoa > k thì tăng x1.
Như vậy thuật toán duyệt sẽ có
độ phức tạp (w2l). Các phần còn lại
chỉ là các bước đơn giản.
Dưới đây là chương trình đã
được 100 điểm của bài toán này trong online
contest.
const
max = 251;
INF = $3F3F3F3F;
var
fi, fo: text;
m, n, k: longint;
cot, a: array [0..max, 0..max] of longint;
dai, left, right, up, down: array [0..max] of longint;
procedure read_data;
var p, x, y, i: longint;
begin
readln(n, m);
readln(p, k);
for i := 1 to p do
begin
readln(y, x);
inc(a[x, y]);
end;
end;
procedure init;
var i, j, u, v: longint;
begin
fillchar(left,sizeof(left), $3F);
fillchar(right, sizeof(right), $3F);
fillchar(up,sizeof(up), $3F);
fillchar(down,sizeof(down), $3F);
for i := 1 to m do
for j := 1 to n do
cot[i, j] := cot[i - 1, j] + a[i, j];
end;
procedure update(x, y, i, j: longint);
var p: longint;
begin
p := 2 * (y - x + 1) + 2 * (j - i + 1);
if down[x] > p then down[x] := p;
if up[y] > p then up[y] := p;
if right[i] > p then right[i] := p;
if left[j] > p then left[j] := p;
end;
procedure process;
var s, i, j, x, y: longint;
begin
for x := 1 to m do
for y := x to m do
begin
for i := 1 to n do dai[i] := cot[y, i] - cot[x - 1, i];
i := 1;
j := i;
s := dai[1];
while i <= n do
begin
while (s < k) and (j < n) do
begin
inc(j);
s := s + dai[j];
end;
if s = k then update(x, y, i, j);
s := s - dai[i];
inc(i);
end;
end;
procedure write_result;
var i, best: longint;
begin
for i := 2 to n do
if left[i - 1] < left[i] then left[i] := left[i - 1];
for i := n - 1 downto 1 do
if right[i] > right[i + 1] then right[i] := right[i + 1];
for i := 2 to m do
if up[i] > up[i - 1] then up[i] := up[i - 1];
for i := m - 1 downto 1 do
if down[i] > down[i + 1] then down[i] := down[i + 1];
best := INF + INF - 1;
for i := 1 to n - 1 do
if left[i] + right[i + 1] < best then
best := left[i] + right[i + 1];
for i := 1 to m - 1 do
if up[i] + down[i + 1] < best then
best := up[i] + down[i + 1];
if best < INF + INF - 1 then writeln(best) else writeln('NO');
end;
begin
read_data;
init;
process;
write_result;
end.
Giải Bài MEAN SEQUENCE - Dãy trung bình
Gọi min[i] và max[i] là miền giá trị của số S[i]
để thỏa mãn dãy m[1] đến m[i – 1]. Ta có m[i – 1] ≤ min[i] ≤ max[i] ≤ m[i] với
i > 1. (miền giá trị bao gồm
cả 2 đầu mút) Ta khởi tạo min[1]
= -∞, max[1] = m[1].
Khi đã biết min[i - 1], max[i – 1] ta sẽ tính
được min[i], max[i] bằng cách lấy đối
xứng đoạn min[i – 1], max[i – 1] qua m[i – 1], rồi
lấy giao của đoạn min[i], max[i] với
đoạn [m[i], +∞). Nếu miền giá
trị của S[i] là rỗng thì kết luận luôn đáp
số bằng 0. Cuối cùng đáp số sẽ là max[n + 1] - min[n + 1] + 1.
Tuy nhiên vấn đề là chúng ta không làm
được mảng 5 000 000 phần tử longint.
Chúng ta có thể nhận thấy, min[i], max[i] đều
được tính từ min[i – 1], max[i –
1] nên chúng ta có thể dùng các biến đơn luân phiên nhau.
Như vậy độ phức tạp là O(n)
bộ nhớ O(1). Dưới đây là chương trình
minh họa:
const
maxN = 5000005;
INF = 1111111111;
var n, res: longint;
procedure process;
var i: longint;
t, bi, bi1, mini, maxi, mini1, maxi1: int64;
x: extended;
begin
res := maxlongint;
readln(n);
readln(x);
bi1 := trunc(x * 2);
mini1 := -INF;
maxi1 := bi1 shr 1;
for i := 2 to n do
begin
readln(x);
bi := trunc(x * 2);
mini := bi1 - maxi1;
maxi := bi1 - mini1;
if 2 * mini - bi > 0 then
begin
writeln('0');
exit;
end;
t := bi shr 1;
if maxi > t then maxi := t;
maxi1 := maxi;
mini1 := mini;
bi1 := bi;
end;
res = maxi - mini + 1;
writeln(res);
end;
begin
process;
end.
Giải
Bài MOUTAINS - Hành trình qua núi
Đây là bài toán thiên về cấu trúc dữ liệu,
cụ thể là interval tree. Mỗi nút trên cây sẽ lưu
thông tin về một đoạn đường ray liên tiếp.
Với nút P lưu thông tin về đoạn [L, R], nút P
sẽ lưu SP là chênh lệch giữa điểm R và L. HP
là độ cao lớn nhất trong đoạn [L, R]. Nếu tính gốc là điểm L.
Nút
P sẽ là lá nếu mọi di đều bằng nhau. Nếu
trường hợp nút P không phải là lá, thì P sẽ có 2
nút con là P1 và P2. P1 lưu thông tin về đoạn [ L, (L + R) div 2 ], P2 lưu thông tin về đoạn
[ (L + R) div 2 + 1, R]. Ta sẽ có SP = SP1 + SP2; HP = max(HP1,
SP1 + HP2). Nếu gọi M là số yêu cầu, cách làm này có
độ phức tạp là O(M*logN), tuy
nhiên bộ nhớ lên đến O(N*logN). Vì
giới hạn N là 1 tỷ, ta sẽ không thể lưu
được. Ta sẽ phải tìm cách khác để
lưu. Ta để ý thấy, M ≤ 100 000. Như
vậy, sẽ có không quá 200 000 đầu mút các đoạn
ray. Ta chỉ cần sửa đổi một chút, nút
P lưu đoạn từ L đến R được
sửa lại thành đoạn từ đầu mút thứ
L đến đầu mút thứ R. Dưới đây là chương
trình mẫu cho bài này. Đây là chương trình viết
bằng C++ của Max Zhou (thí sinh Trung Quốc trong cuộc
thi IOI online)
#include
#include
#include
#define INFINITY 1000000000
struct Titem {
int oper;
int L, R, v;
};
struct Tnode {
int L, R;
int fm, sum, v;
bool used;
int Lch, Rch;
};
void init();
void prefix();
void solve();
void createtree(int r, int L, int R);
void inserttree(int r, int L, int R, int v);
int findtree(int r, int limit);
inline int count(int r);
int n;
int nitem;
Titem item[110000];
int nlist, list[210000];
int nnode;
Tnode tree[410000];
int main() {
init();
prefix();
solve();
return 0;
}
void init() {
char line[1000];
int L, R, v;
scanf('%d', &n);
while ( scanf('%s', line)==1 )
if ( strcmp(line, 'I')==0 ) {
scanf('%d %d %d', &L, &R, &v);
item[nitem].oper=0; item[nitem].L=L; item[nitem].R=R; item[nitem].v=v;
++nitem;
}
else if ( strcmp(line, 'Q')==0 ) {
scanf('%d', &v);
item[nitem].oper=1; item[nitem].v=v;
++nitem;
}
else break;
}
void prefix() {
int i;
for ( i=0; i
if ( item[i].oper==0 ) {
list[nlist++]=item[i].L; list[nlist++]=item[i].R+1;
}
list[nlist++]=1; list[nlist++]=n+1;
std::sort(list, list+nlist);
nlist=std::unique(list, list+nlist)-list;
for ( i=0; i
if ( item[i].oper==0 ) {
item[i].L=std::lower_bound(list, list+nlist, item[i].L)-list;
item[i].R=std::lower_bound(list, list+nlist, item[i].R+1)-list-1;
}
}
void solve() {
int i;
tree[nnode].fm=-INFINITY; ++nnode;
createtree(1, 0, nlist-2);
for ( i=0; i
if ( item[i].oper==0 ) inserttree(1, item[i].L, item[i].R,
item[i].v);
else {
int res = findtree(1, item[i].v);
printf('%dn', res);
}
}
void createtree(int r, int L, int R) {
tree[r].L=L; tree[r].R=R;
tree[r].fm=tree[r].sum=0; tree[r].used=false;
tree[r].Lch=tree[r].Rch=0;
if ( L
tree[r].Lch=++nnode; createtree(nnode, L, (L+R)/2);
tree[r].Rch=++nnode; createtree(nnode, (L+R)/2+1, R);
}
}
void update(int r) {
if ( tree[r].used ) {
tree[r].sum=count(r)*tree[r].v;
tree[r].fm=std::max(tree[r].v, tree[r].sum);
}
else {
int Lch = tree[r].Lch, Rch = tree[r].Rch;
tree[r].sum=tree[Lch].sum+tree[Rch].sum;
tree[r].fm=std::max(tree[Lch].fm, tree[Lch].sum+tree[Rch].fm);
}
}
void inserttree(int r, int L, int R, int v) {
if ( L<=tree[r].L && R>=tree[r].R ) {
tree[r].used=true; tree[r].v=v; update(r);
return;
}
int Lch = tree[r].Lch, Rch = tree[r].Rch;
if ( tree[r].used && tree[r].L
tree[Lch].used=true; tree[Lch].v=tree[r].v; update(Lch);
tree[Rch].used=true; tree[Rch].v=tree[r].v; update(Rch);
}
tree[r].used=false;
if ( L<=(tree[r].L+tree[r].R)/2 ) inserttree(Lch, L, R, v);
if ( R>(tree[r].L+tree[r].R)/2 ) inserttree(Rch, L, R, v);
update(r);
}
int findtree(int r, int limit) {
if ( tree[r].used || tree[r].L==tree[r].R )
if ( tree[r].v<=0 ) return count(r);
else return std::min(limit/tree[r].v, count(r));
int Lch = tree[r].Lch, Rch = tree[r].Rch;
if ( tree[tree[r].Lch].fm<=limit )
return count(Lch)+findtree(Rch, limit-tree[Lch].sum);
else
return findtree(Lch, limit);
}
inline int count(int r) {
int L = tree[r].L, R = tree[r].R;
return list[R+1]-list[L];
}
Giải bài BIRTHDAY - Ngày
sinh nhật
Đề
bài yêu cầu sắp xếp lại chỗ ngồi của
những đứa trẻ sao cho khoảng cách mà
đứa trẻ phải di chuyển xa nhất là ngắn
nhất có thể được. Chúng ta nên lưu ý có
2 cách sắp xếp cuối cùng: thuận chiều kim đồng hồ và ngược chiều
kim đồng hồ. Ta có nhận xét là hai trường
hợp này được giải quyết như nhau, nên ta
chỉ giải quyết trường hợp thuận
chiều kim đồng hồ:
Gọi a[i]
là vị trí ban đầu của những đứa
trẻ. Chúng ta chuyển đứa trẻ
thứ i đến vị trí i. Đặt d[i] là một
số thể hiện hướng và khoảng cách
đứa trẻ i phải di chuyển.
• |d[i]| =
khoảng cách di chuyển của đứa trẻ thứ
i.
• d[i] > 0
nếu di chuyển cùng chiều kim
đồng hồ.
• d[i] < 0 nếu di chuyển ngược
chiều kim đồng hồ.
• Nếu
khoảng cách d[i] bằng N/2 (N chẵn) thì ưu tiên di
chuyển thuận chiều kim
đồng hồ.
Ta có: -((N –
1) div 2) ≤ d[i] ≤ N div 2
Nếu
mỗi đứa trẻ được dịch sang
phải một đơn vị, thì d[i] sẽ thay
đổi theo
• Nếu
d[i] ≤ N div 2 thì d[i] = d[i] + 1.
• Nếu
d[i] = N div 2 thì d[i] = -((N – 1) div 2)
Nhiệm
vụ của chúng ta là xoay cách đứa trẻ thêm
một số lần để sao cho max(|d[i]|) là min. Chúng ta
nhận thấy có thể tính được giá trị này
trong thời gian O(n). Xét C là đoạn liên tiếp dài
nhất thuộc [-((N – 1) div 2), N div 2] mà không có d[i] nào
xuất hiện. Chú ý đoạn dài nhất có thể là [a,
N div 2] hợp [-((N – 1) div 2), b] với b < a. Nếu C có P
phần tử thì đáp số sẽ là (N – P) div 2.
Dưới
đây là bài giải đã được 100 điểm.
#include
#include
#include
#define MAXN
1000001
#define Swap(x,
y) ((x) ^= (y), (y) ^= (x), (x) ^= (y))
int a[MAXN], N,
i, j;
int u[MAXN];
void Reverse(void)
{ int i;
for (i = 0; i
<= (N - 2) / 2; i ++)
Swap(a[i], a[N
- i - 1]);
}
int
GoodMin(void)
{ int i, j,
first, last, max_gap = 0;
memset(u, 0,
sizeof(u));
for (i = 0; i
< N; i ++)
{ j = a[i] - i;
while (j <
0) j += N;
u[j] = 1;
}
for (i = 0;
u[i] == 0; i ++);
first = last =
i;
for (++ i; i
< N; i ++)
if (u[i])
{
if (i - last
> max_gap) max_gap = i - last;
last = i;
}
if (N - last +
first > max_gap)
max_gap = N -
last + first;
return (N -
max_gap + 1) / 2;
}
void
GoodSolve(void)
{
int Ans1, Ans2;
Ans1 =
GoodMin();
Reverse();
Ans2 =
GoodMin();
printf("%dn",
Ans1 < Ans2? Ans1 : Ans2);
}
int main(void)
{
//
freopen("bir.in", "r", stdin);
scanf("%d",
&N);
for (i = 0; i
< N; i ++)
{
scanf("%d",
&(a[i]));
-- a[i];
}
GoodSolve();
return 0;
}
Giải
Bài RECTANGLE GAME - Trò chơi cắt hình chữ nhật
Ta có một vài định nghĩa sau:
• Một trạng thái của bảng được
thể hiện bằng cặp số (n, m).
• Một trạng thái P được gọi là trạng
thái thắng nếu ta luôn có cách thắng mặc cho
bước tiếp theo đối
thủ đi thế nào.
• Một trạng thái P được gọi là trạng
thái thua nếu đối thủ luôn có cách thắng mặc
cho các bước tiếp theo ta đi
thế nào.
Theo định nghĩa trên:
• (1, 1) là trạng thái thua.
• Một trạng thái thắng nếu có tồn tại ít
nhất một nước đi dẫn đến
trạng thái thua.
• Một trạng thái thua mọi nước đi tiếp theo đều hướng đến
một trạng thái thắng.
Chúng ta có thể lập một bảng như
sau, vị trí i j là dấu * thì trạng thái (i, j) là trạng
thái thua và ngược lại.
Sau khi phân
tích, chúng ta có thể rút ra một nhận xét như sau:
Trạng thái (n, m) là trạng thái thua khi và chỉ khi (m + 1) =
2k (n + 1). Ta sẽ chứng minh nhận xét này:
Trường hợp k = 0 ↔ m = n.
• m = n = 1: (m, n) là trạng thái thua theo
định nghĩa.
• m > 1: Nếu đối thủ
đưa ta vào trạng thái (n, p) thì m/2 ≤ p < m.
Vậy ta có thể đi từ trạng thái (n, p)
đến trạng thái (p, p) một trạng thái thua.
Trường hợp k ≠ 0. Không mất tính tổng quát giả sử k > 0.
Vì (m + 1) = 2k (n + 1) ↔ (n + 1) = 2-k(m + 1). Khi đang
ở trạng thái (n, m) ta sẽ có hai hướng: (p, m)
hoặc (n, q):
• Nếu sau khi cắt, ta đến trạng thái (p, m). Ta có
n/2 ≤ p < n. Mà n = 2k (m + 1) – 1 nên ta có bất
đẳng thức sau: 2k-1(m + 1) – 1 < p < 2k(m + 1) – 1. Như vậy,
người tiếp theo có thể
thực hiện nước đi từ trạng thái (p, m) đến
trạng thái (2k-1(m+1) – 1, m).
• Nếu sau khi cắt, ta đến trạng thái (n, q) trong
đó m/2 ≤ q < m. Ta sẽ chứng minh không tồn
tại số nguyên thỏa mãn n = 2i(q
+ 1) – 1. Ta sẽ chứng minh bằng phản chứng. Giả
sử tồn tại số nguyên i thỏa mãn đẳng
thức n = 2i(q + 1) – 1.
- Ta có n = 2k(m + 1) – 1 và m > q nên i > k.
- Mặt khác, m/2 ≤ q, ta có:
- 2k(m + 1) – 1 = n = 2i(q+1) – 1 ≥
2i(m/2 + 1) – 1 = 2i -1(m + 2) > 2i-1 (m + 1) – 1
- ↔ k > i – 1 ↔ i < k + 1
i là số nguyên và k < i < k + 1 (vô lý).
Vì vậy, nếu m + 1 = 2k(n + 1)
thì trạng thái này là trạng thái thua. Nhiệm vụ
của chúng ta trong mỗi lần thực hiện một
nước đi từ (n, m) đến (n’, m’) sao cho m’ + 1
= 2i (n’ + 1). Không mất tính tổng quát, ta giả
sử n ≥ m. Ta sẽ có chọn m’, n’ sao cho:
• m’ = m
• n’ = 2k (m’ + 1) – 1, lớn nhất và nhỏ hơn
n.
Độ phức tạp của thuật toán trong
trường hợp xấu nhất là O(n log n)
uses preclib;
var
x, y, m: longint;
a: array [1..100] of longint;
procedure make(u, v: longint);
begin
if ođ(v) then
v := v div 2 + 1
else
v := v div 2;
m := 1;
a[1] := u;
while a[m] < v do
begin
inc(m);
a[m] := a[m - 1] * 2 + 1;
end;
end;
begin
while true do
begin
x := dimension_x;
y := dimension_y;
if (x > y) and (2 * y >= x) then
begin
cut(vertical, y);
continue;
end;
if (y > x) and (2 * x >= y) then
begin
cut(horizontal, x);
continue;
end;
if x > y then make(y, x) else make(x, y);
if x > y then
cut(vertical, a[m])
else
cut(horizontal, a[m]);
end;
end.
Giải Bài RIVER - Các dòng sông
Đây là một bài
toán quy hoạch động trên cây khá hay. Trước
tiên, chúng ta cần xây dựng một cây mà mỗi nút trên
cây, chỉ có duy nhất một đường đến
gốc (Byteland town). v là cha của u
nếu v là ngôi làng đầu tiên trên đường đi
từ u đến gốc.
Gọi
r là gốc của cây (Byteland town). Đặt depth(u)
là số cạnh trên đường đi từ u
đến r. Ta có thể tính được depth(u) trong
O(n). Đặt deg(u) là số con của
u và số cây gỗ bị cắt ở nút u là trees(u).
Hàm quy hoạch
động A[v, t, p] với ý nghĩa chi
phí ít nhất của việc xây t nhà máy trong cây con có gốc
là v và những cây gỗ mà không được xử lý
ở trong cây con v, thì sẽ trôi đến nút p (p nằm
trên đường từ v đến r). Chúng ta sẽ tính
A[v, t, p] với mỗi v và 0 ≤ t ≤ k. Ta sẽ tính
được A[v, t, p] theo công thức sau:
• 0 nếu cây con
gốc v có đúng t nút
• min(A1[v, t, p], A2[v,
t]) trong trường hợp còn lại
trong đó
• A1[v, t, p] là chi phí ít
nhất của việc xây dựng t nhà máy trong cây con có
gốc là v, không xây nhà máy tại nút v và những cây gỗ
mà không được xử lý ở trong cây con v, thì sẽ
trôi đến nút p (p nằm trên đường từ v
đến r).
• A2[v,
t] là chi phí ít nhất của việc xây dựng t nhà máy trong
cây con có gốc là v và tại v có xây một nhà máy.
Gọi d = deg(v) và
vi là các con của v. Ta sẽ tính A1[v, t, p] và A2[v, t] theo công
thức sau:
• A1[v, t, p] = trees(v)
* khoảng cách(v, p) + min( ∑i=1..d A[vi, ti,
p]) thỏa mãn ∑ti = t.
• A2[v, t] = min
(∑i=1..d A[vi, ti, depth(v)]) thỏa mãn
∑ti = t – 1.
Nhìn vào 2 công
thức trên, ta sẽ thấy ngay rằng, chúng ta cần
phải xét mọi cách chia t nhà máy vào các cây con của v. Trong
trường hợp nút v có nhiều nút con, chúng ta cần
phải có một thuật toán tốt hơn là duyệt.
Chúng ta sẽ cần đến một hàm quy hoạch
động tiếp theo:
• B[i,
s, v, p] là chi phí ít nhất để xây s nhà máy trong i cây con
gốc v1, v2, v3, …, vi của
v. Những cây gỗ không được xử lý ở
trong cây con v, sẽ trôi đến nút p (p nằm trên
đường từ v đến r).
• C[i, s, v] với i,
s, v có ý nghĩa tương tự như trên nhưng
điểm khác là những cây gỗ chưa được
xử lý sẽ được chuyển đến một
nhà máy đặt tại v.
Ta sẽ tính
được mảng B theo công thức sau:
• B[0, s, v, p] = 0
• B[i, s, v, p] = min (B[i
– 1, s – j, v, p] + A[vi, j, p]) với 0 ≤ j ≤ s.
Còn mảng C sẽ
được tính theo công thức sau:
• C[0, s, v] = 0
• C[i, s, v] = min (C[i –
1, s – j, v] + A[vi, j, depth(v)]) với 0 ≤ j ≤ s.
Dựa vào ý nghĩa
A1, A2, B, C ta có thể nhận thấy:
• A1[v, t, p] = B[deg(v),
t, v, p]
• A2[v, t] = C[deg(v), t
– 1, v]
Để tính
mọi giá trị A1[v, t, p] (cũng như A2[v, t]) với p
thuộc{0..depth(v)}, chúng ta tính B[i, s, v, p] (cũng như C[i,
s, v]) với i = 0,…,deg(v) và s = 0,…,k. Như vậy với
mỗi cặp v, p ta tính được trong O(k2(deg(v)
+ 1)). Để tính toàn bộ A, B, C ta mất O(n∑k2(deg(v)
+ 1)) = O(k2n2) vì ∑deg(v) = n – 1.
Đáp
số cuối cùng là A1[r, k, 0].
Dưới đây
là toàn bộ chương trình:
program riv;
const
maxn = 100;
maxk = 50;
var
lch, fch, next, w, d :
array [0..maxn] of integer;
f1, f2 : array [1..maxn,
0..maxn, -1..maxk] of longword;
dis : array [0..maxn,
0..maxn] of longword;
maxcost, maxDword :
longword;
n, k : integer;
procedure reađata;
var
i, fa : integer;
begin
readln(n, k);
for i := 1 to n do begin
readln(w[i], fa, d[i]);
if fch[fa] = 0 then begin
fch[fa] := i;
lch[fa] := i;
end
else begin
next[lch[fa]] := i;
lch[fa] := i;
end;
end;
end;
function min(x, y :
double) : double;
begin
if x < y then min := x
else min := y;
if min > maxDword then
min := maxDword;
end;
procedure dp2(i, grand, k
: integer); forward;
procedure dp1(i, grand, k
: integer);
begin
if f1[i, grand, k]
<> maxDword then exit;
if fch[i] <> 0 then
begin
dp2(fch[i], grand, k);
dp2(fch[i], i, k-1);
f1[i, grand, k] :=
round(min(f2[fch[i], grand, k] + dis[i, grand] * w[i], f2[fch[i], i, k-1]));
end
else
if k = 1 then
f1[i, grand, k] := 0
else if k = 0 then
f1[i, grand, k] :=
round(min(dis[i, grand] * w[i], maxcost))
else
f1[i, grand, k] :=
maxcost;
end;
procedure dp2(i, grand, k
: integer);
var
k1, k2 : integer;
begin
if k = -1 then begin
f2[i, grand, k] :=
maxcost;
exit;
end;
if f2[i, grand, k]
<> maxDword then exit;
if next[i] <> 0 then
begin
k2:=k;
for k1 := 0 to k do begin
dp1(i, grand, k1);
dp2(next[i], grand, k2);
f2[i, grand, k] :=
round(min(f2[i, grand, k], f1[i, grand, k1] + f2[next[i], grand, k2]));
dec(k2);
end
end
else begin
dp1(i, grand, k);
f2[i, grand, k] := f1[i,
grand, k];
end;
end;
procedure dfs(root, i :
integer; cost : longword);
var
ch : integer;
begin
dis[i, root] := cost;
ch := fch[i];
while ch <> 0 do
begin
dfs(root, ch, cost +
d[ch]);
ch := next[ch];
end;
end;
procedure init;
var
i, j : integer;
begin
for i := 0 to n do dfs(i,
i, 0);
maxDword := not maxDword;
fillDword(f1,sizeof(f1)
shr 2,maxDword);
fillDword(f2,sizeof(f2)
shr 2,maxDword);
maxcost := 2000000001;
end;
begin
reađata;
init;
dp2(fch[0], 0, k);
writeln(f2[fch[0], 0,
k]);
end.