• <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 閱讀(318) 評論(0)  編輯 收藏 引用
            <2009年4月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            精品久久久久久无码不卡| 久久精品国产久精国产果冻传媒| 麻豆AV一区二区三区久久| 伊人色综合久久天天人手人婷| 日本久久久久亚洲中字幕| 99精品久久精品| 精品久久久一二三区| 久久国产精品成人影院| 国产精品99久久久久久董美香| 伊人久久大香线蕉综合网站| 久久99精品国产麻豆| 久久精品免费大片国产大片| 色综合久久无码中文字幕| 国产精品一区二区久久精品无码 | 99久久国产综合精品五月天喷水| 伊人久久大香线蕉综合5g| 久久久精品免费国产四虎| 99久久99久久精品国产片果冻| 国产午夜精品久久久久九九电影| 性欧美大战久久久久久久久| 久久久受www免费人成| 99久久无色码中文字幕| 亚洲国产一成人久久精品| 午夜精品久久久久久影视777| 国产精品九九久久免费视频| 久久青青草原精品国产| 久久精品国产精品亚洲精品| 一本色道久久综合| 欧美午夜A∨大片久久| 久久精品亚洲乱码伦伦中文| 久久午夜电影网| 青青国产成人久久91网| 久久精品成人免费网站| 国产精品久久久亚洲| 国产综合久久久久久鬼色| 久久狠狠高潮亚洲精品| 潮喷大喷水系列无码久久精品| 久久综合狠狠综合久久| 精品久久人妻av中文字幕| 久久精品无码午夜福利理论片| 久久精品www人人爽人人|