• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 74,  comments - 33,  trackbacks - 0
            Cell Phone Network
            Time Limit: 1000MS Memory Limit: 65536K
            Total Submissions: 1440 Accepted: 443

            Description

            Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.

            Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ AN; 1 ≤ BN; AB) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.

            Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

            Input

            * Line 1: A single integer: N
            * Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

            Output

            * Line 1: A single integer indicating the minimum number of towers to install

            Sample Input

            5
            1 3
            5 2
            4 3
            3 5
            

            Sample Output

            2
            

            Source

            USACO 2008 January Gold
            今天軟件工程的時候想通了這道題目成功的把3中狀態和DP聯系起來,以前思考的時候一直從root想leaves執行程序,而下午仔細想想如果從root出發,而執行程序的時候無法統計最后的點數,更可怕的是不是root影響leaves而是leaves影響著root的取值達到最優值!而這道題就是這樣可以計算下利用DFS遍歷Tree我們知道DFS時間度為O(n)空間上用鄰接表記錄關系圖,O(n)
            說下3中狀態轉移,我就不講了,我這人口才不好,看寫的比說的清楚,哈哈~~
            第一種狀態:就是一個節點不放置塔,而它的所有leaves被覆蓋,當然它自己能被它的leaves控制。
            第二種狀態:一個節點和它的所有leaves全被覆蓋,而這個節點放置控制塔。
            第三種狀態:一個節點暫時沒有被覆蓋,也沒有放置節點。
            DFS函數如下:
            void?DFS(int?x){
            ????
            int?i,sign,flag;
            ????
            for(flag=sign=i=0;i<v[x].size();i++){
            ????????
            int?t=v[x][i];
            ???????????
            if(!mark[t]){
            ????????????sign
            =1;mark[t]=1;
            ????????????DFS(v[x][i]);
            ????????????
            if(dp[t][0]<dp[t][1])dp[x][0]+=dp[t][0];
            ?????????????
            else?{
            ??????????????????dp[x][
            0]+=dp[t][1];
            ??????????????????sign
            =1;
            ?????????????}

            ?????????????dp[x][
            1]+=getmin(getmin(dp[t][0],dp[t][1]),dp[t][2]);
            ?????????????dp[x][
            2]+=dp[t][0];
            ???????????}

            ????}

            ????
            if(!sign)dp[x][0]=dp[x][1]=1;
            ????
            else{
            ????????dp[x][
            1]++;
            ???????????
            if(!flag)dp[x][0]+=1;
            ????}

            }
            posted on 2009-04-09 21:45 KNIGHT 閱讀(319) 評論(0)  編輯 收藏 引用
            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久国产精品福利免费| 久久五月精品中文字幕| AV无码久久久久不卡蜜桃| 2020久久精品国产免费| 久久久久久国产a免费观看不卡| 国产精品久久久久久久久久影院 | 人妻无码久久精品| 中文字幕无码免费久久| 久久综合综合久久综合| 久久国产劲爆AV内射—百度| 久久久久久青草大香综合精品| 久久久亚洲裙底偷窥综合| 久久综合久久久| 一本色道久久99一综合| 久久无码人妻精品一区二区三区| 国产亚洲精久久久久久无码| 久久久久久毛片免费播放| 2021国内久久精品| 国产亚洲色婷婷久久99精品91| www亚洲欲色成人久久精品| 国产精品久久久久乳精品爆| 午夜天堂精品久久久久| 久久亚洲精品人成综合网| 亚洲人成无码网站久久99热国产| 亚洲精品成人网久久久久久| 99久久婷婷国产综合亚洲| 午夜久久久久久禁播电影| 亚洲综合久久夜AV | 久久亚洲中文字幕精品一区| 91精品国产91久久久久久青草| 久久久久久青草大香综合精品 | 99久久国产亚洲高清观看2024| 天天爽天天狠久久久综合麻豆 | 久久被窝电影亚洲爽爽爽| 51久久夜色精品国产| 国产成人精品久久一区二区三区| 亚洲国产精品无码久久一区二区 | 久久精品a亚洲国产v高清不卡| 人妻无码久久一区二区三区免费| 一本色道久久HEZYO无码| 亚洲国产精品成人久久|