2013-09-15 20:04
題目描述
有這樣一個游戲,桌面上擺了N枚硬幣,分別標號1-N,每枚硬幣有一個分數C[i]與一個后繼硬幣T[i]。作為游戲參與者的你,可以購買一個名為mlj的小機器人,從任一個硬幣處開始游戲,然后跳往該硬幣的后繼硬幣T[i],直到你要它停下來,經過每個硬幣時,你可以選擇是否撿起它。當某個mlj機器人停下來后將被扔掉,這時你可以選擇結束游戲或再買一個mlj機器人繼續游戲。
注意,每個硬幣只能撿一次,而且你不能要求mlj跳向一個已被撿起的硬幣或從一個已被撿起的硬幣處開始游戲,因為那樣會把mlj摔壞的。
?
Your?Task
一開始你的得分是0,每購買一個mlj機器人將扣掉你M分,撿起一個硬幣將得到對應的分數C[i],請問如何使得分盡量高(游戲過程中分數可以為負)。
?
輸入文件
第一行兩個正整數?N?M
接下來N行,每行兩個正整數C[i]?T[i]。
輸出文件
?????一個整數,最大得分。
?
樣例輸入
? 4?2
?1?3
?2?3
?1?4
?1?3
樣例輸出
? 2
?
數據約定
30%???N<=10
60%???N<=300
100???N<=100000??1<=T[i]<=N
運算過程及結果均在Longint范圍內
?
因為有N個點,N條邊,且每個點都只有一個后繼,所以可推知圖中一定存在環,所以先用tarjan縮點,得到一顆上寬下窄的樹(因為一個點只能有一個后繼,而每個點可以成為好多點的后繼),為了DP方便,縮點重新建圖時,將邊反向,這時得到了一顆多叉樹,考慮到可能出現森林,所以用一個總根節點將每顆多叉樹的根節點連接起來。
然后我們得到了一顆多叉樹,問題轉化成了樹形DP,由題意可知,因為到一個硬幣可以不撿,所以機器人的路徑可以重合,那么設W(X)代表從X節點向下走可以取得的最大值,假設X有多個兒子,因為當前有一個機器人由上方走來到X節點,所以X節點的兒子中最大的不用X重新買機器人,剩下的兒子中,如果W(P)>M,就相當于在P兒子處再買一個機器人,那么更新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 .
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
