2013-09-15 20:04
題目描述
有這樣一個(gè)游戲，桌面上擺了N枚硬幣，分別標(biāo)號(hào)1-N，每枚硬幣有一個(gè)分?jǐn)?shù)C[i]與一個(gè)后繼硬幣T[i]。作為游戲參與者的你，可以購(gòu)買(mǎi)一個(gè)名為mlj的小機(jī)器人，從任一個(gè)硬幣處開(kāi)始游戲，然后跳往該硬幣的后繼硬幣T[i]，直到你要它停下來(lái)，經(jīng)過(guò)每個(gè)硬幣時(shí)，你可以選擇是否撿起它。當(dāng)某個(gè)mlj機(jī)器人停下來(lái)后將被扔掉，這時(shí)你可以選擇結(jié)束游戲或再買(mǎi)一個(gè)mlj機(jī)器人繼續(xù)游戲。
注意，每個(gè)硬幣只能撿一次，而且你不能要求mlj跳向一個(gè)已被撿起的硬幣或從一個(gè)已被撿起的硬幣處開(kāi)始游戲，因?yàn)槟菢訒?huì)把mlj摔壞的。
?
Your?Task
一開(kāi)始你的得分是0，每購(gòu)買(mǎi)一個(gè)mlj機(jī)器人將扣掉你M分，撿起一個(gè)硬幣將得到對(duì)應(yīng)的分?jǐn)?shù)C[i]，請(qǐng)問(wèn)如何使得分盡量高（游戲過(guò)程中分?jǐn)?shù)可以為負(fù)）。
?
輸入文件
第一行兩個(gè)正整數(shù)?N?M
接下來(lái)N行，每行兩個(gè)正整數(shù)C[i]?T[i]。
輸出文件
?????一個(gè)整數(shù)，最大得分。
?
樣例輸入
? 4?2
?1?3
?2?3
?1?4
?1?3
樣例輸出
? 2
?
數(shù)據(jù)約定
30%???N<=10
60%???N<=300
100???N<=100000??1<=T[i]<=N
運(yùn)算過(guò)程及結(jié)果均在Longint范圍內(nèi)
?
因?yàn)橛蠳個(gè)點(diǎn)，N條邊，且每個(gè)點(diǎn)都只有一個(gè)后繼，所以可推知圖中一定存在環(huán)，所以先用tarjan縮點(diǎn)，得到一顆上寬下窄的樹(shù)（因?yàn)橐粋€(gè)點(diǎn)只能有一個(gè)后繼，而每個(gè)點(diǎn)可以成為好多點(diǎn)的后繼），為了DP方便，縮點(diǎn)重新建圖時(shí)，將邊反向，這時(shí)得到了一顆多叉樹(shù)，考慮到可能出現(xiàn)森林，所以用一個(gè)總根節(jié)點(diǎn)將每顆多叉樹(shù)的根節(jié)點(diǎn)連接起來(lái)。
然后我們得到了一顆多叉樹(shù)，問(wèn)題轉(zhuǎn)化成了樹(shù)形DP，由題意可知，因?yàn)榈揭粋€(gè)硬幣可以不撿，所以機(jī)器人的路徑可以重合，那么設(shè)W(X)代表從X節(jié)點(diǎn)向下走可以取得的最大值，假設(shè)X有多個(gè)兒子，因?yàn)楫?dāng)前有一個(gè)機(jī)器人由上方走來(lái)到X節(jié)點(diǎn)，所以X節(jié)點(diǎn)的兒子中最大的不用X重新買(mǎi)機(jī)器人，剩下的兒子中，如果W(P)>M，就相當(dāng)于在P兒子處再買(mǎi)一個(gè)機(jī)器人，那么更新W(X)值，W(X):=W(P)-M;
{
$m 500000000
}
//
By BLADEVIL
var
n, m :longint;
father :
array
[
0
..
200010
]
of
longint;
start :longint;
flag, fseq :
array
[
0
..
100010
]
of
boolean;
stack :
array
[
0
..
100010
]
of
longint;
tot :longint;
time :longint;
low, dfn :
array
[
0
..
100010
]
of
longint;
key :
array
[
0
..
100010
]
of
longint;
color :longint;
pre, last, other :
array
[
0
..
200010
]
of
longint;
l :longint;
mark :
array
[
0
..
200010
]
of
longint;
ans :longint;
function
min(a,b:longint):longint;
begin
if
a>b
then
min:=b
else
min:=
a;
end
;
procedure
connect(x,y:longint);
begin
inc(l);
pre[l]:
=
last[x];
last[x]:
=
l;
other[l]:
=
y;
end
;
procedure
dfs(x:longint);
var
cur :longint;
begin
inc(tot);
stack[tot]:
=
x;
flag[x]:
=
true;
fseq[x]:
=
true;
inc(time);
dfn[x]:
=
time;
low[x]:
=
time;
cur:
=
other[last[x]];
if
not
flag[cur]
then
begin
dfs(cur);
low[x]:
=
min(low[x],low[cur]);
end
else
if
fseq[cur]
then
low[x]:=
min(low[x],dfn[cur]);
cur:
=-
1
;
if
dfn[x]=low[x]
then
begin
inc(color);
while
cur<>x
do
begin
cur:
=
stack[tot];
dec(tot);
fseq[cur]:
=
false;
key[cur]:
=
color;
mark[color]:
=mark[color]+
mark[cur];
end
;
end
;
end
;
procedure
init;
var
i :longint;
x :longint;
p :longint;
begin
read(n,m); tot:
=
0
; color:=
n;
for
i:=
1
to
n
do
father[i]:=
i;
for
i:=
1
to
n
do
begin
read(mark[i],x);
connect(i,x);
father[x]:
=
i;
end
;
for
i:=
1
to
n
do
if
father[i]=i
then
start:=
i;
if
start=
0
then
inc(start);
dfs(start);
for
i:=
1
to
n
do
if
key[i]=
0
then
dfs(i);
for
i:=
1
to
n
do
begin
p:
=
other[last[i]];
if
key[i]<>key[p]
then
begin
connect(key[p],key[i]);
father[key[i]]:
=
key[p];
end
;
end
;
for
i:=n+
1
to
color
do
if
father[i]=
0
then
connect(color+
1
,i);
end
;
function
w(x:longint):longint;
var
p, q :longint;
i, j, maxx :longint;
sum :longint;
begin
q:
=
last[x];
j:
=
0
;
w:
=
0
;
w:
=w+
mark[x];
maxx:
=
0
;
while
q<>
0
do
begin
p:
=
other[q];
sum:
=
w(p);
if
sum>m
then
w:=w+sum-
m;
if
sum>maxx
then
maxx:=
sum;
q:
=
pre[q];
end
;
if
maxx<m
then
w:=w+maxx
else
w:=w+
m;
end
;
begin
assign(input,
'
coin.in
'
); reset(input);
assign(output,
'
coin.out
'
); rewrite(output);
init;
ans:
=w(color+
1
)-
m;
if
ans>
0
then
writeln(ans)
else
writeln(
0
);
close(input); close(output);
end
.
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
