亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

硬幣問題 tarjan縮點+DP 莫濤

系統 2307 0

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
      
      .
    

?

硬幣問題 tarjan縮點+DP 莫濤


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲欧美日韩高清一区二区一 | 久久精品卫校国产小美女 | 涩涩伊人 | 色综合夜夜嗨亚洲一二区 | 一级特黄aa大片一又好看 | 综合网伊人 | 日本黄色小视频在线观看 | 91成人啪国产啪永久地址 | 人人狠狠综合久久亚洲 | 手机在线看福利 | 免费福利小视频 | 亚州免费一级毛片 | 欧美成人精品 | 中文字幕亚洲一区二区v@在线 | 日韩久久一区二区三区 | 日韩一区二区不卡中文字幕 | 日韩欧美一二区 | 欧美成人全部免费观看1314色 | 久久久噜久噜久久综合 | 97av视频| 久久99精品久久久久久 | 2020国产精品永久在线观看 | 亚洲欧美日韩中文综合在线不卡 | 久久精品视频16 | 国产欧美精品一区二区三区-老狼 | 看a网站| 香蕉亚洲| 豆国产93在线 | 亚洲 | 久久www视频 | 888米奇色狠狠俺去啦 | 国产高清视频在线 | 男人懂的网站 | 国产日韩欧美在线观看不卡 | 日韩一区二区三区在线免费观看 | 视频一区免费 | 狠狠色噜噜狠狠米奇777 | 狠狠色丁香婷婷综合小时婷婷 | www国产精品 | 国产成人视屏 | 99综合网 | 99久久网站 |