• <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>
            隨筆-65  評論-6  文章-0  trackbacks-0
             1 //狀態轉移方程:    dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son[i]][k])    
             2 //                    以第i個城市為起點,攻占j個城市的最大收益
             3 
             4 #include <iostream>
             5 #include <cstring>
             6 using namespace std;
             7 #define MaxSize 205
             8 
             9 int dp[MaxSize][MaxSize];
            10 int value[MaxSize];
            11 int mapmap[MaxSize][MaxSize];
            12 bool vis[MaxSize];
            13 int n,m;
            14 
            15 inline int max(int a,int b){
            16     return a>b?a:b;
            17 }
            18 
            19 void dfs(int root){
            20     int i,j,k,u;
            21     dp[root][1]=value[root];
            22     for(i=1;i<=mapmap[root][0];i++){
            23         u=mapmap[root][i];//root之后可以選擇攻占的城市
            24         dfs(u);
            25         for(j=m+1;j>0;j--){
            26             for(k=1;k+j<=m+1;k++){
            27                 dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[u][k]);
            28             }
            29         }
            30     }
            31 }
            32 
            33 int main(){
            34     //freopen("in.txt","r",stdin);
            35     int i;
            36     while (scanf("%d%d",&n,&m),(n||m)){
            37         for(i=0;i<=n;i++)
            38             mapmap[i][0]=0;
            39         value[0]=0;
            40         for(i=1;i<=n;i++){
            41             int a;
            42             scanf("%d %d",&a,&value[i]);
            43             mapmap[a][0]++;
            44             mapmap[a][mapmap[a][0]]=i;
            45         }
            46         memset(dp,0,sizeof(dp));
            47         //問題的關鍵在于將0作為第零個城堡,價值為零,這樣就可以實現大一統!
            48         dfs(0);
            49         printf("%d\n",dp[0][m+1]);//加入了第零個城堡,則m+1
            50     }
            51     return 0;
            52 }
            posted on 2012-07-12 22:15 Leo.W 閱讀(512) 評論(1)  編輯 收藏 引用

            評論:
            # re: hdu 1561(The more, The Better) 2012-07-23 10:58 | 77
            for(j=m+1;j>0;j--)
            為什么j 從大到小而不是從小到大?  回復  更多評論
              
            精品久久久久久久久免费影院| 国产巨作麻豆欧美亚洲综合久久| 欧美日韩精品久久久久| 亚洲人成网站999久久久综合 | 久久精品一区二区国产| 丁香五月综合久久激情| 久久久久久亚洲精品无码| 亚洲国产精品久久电影欧美| 少妇久久久久久被弄高潮| 伊人色综合久久| 久久91精品国产91| 国产精品久久久久9999高清| 日韩电影久久久被窝网| 久久91精品国产91久久麻豆| 青青热久久国产久精品| 久久99精品国产麻豆| 亚洲精品国产自在久久| 久久99热国产这有精品| 久久久久久久91精品免费观看| 久久精品国产亚洲沈樵| 中文字幕无码精品亚洲资源网久久 | 久久久女人与动物群交毛片| 精品久久久久久99人妻| 97久久综合精品久久久综合| 久久婷婷午色综合夜啪| 久久久久久久综合综合狠狠| 久久中文字幕一区二区| 国产99精品久久| 无码人妻少妇久久中文字幕蜜桃 | 国产精品免费久久| 72种姿势欧美久久久久大黄蕉| 国产69精品久久久久9999APGF| 亚洲精品国精品久久99热| 久久精品夜色噜噜亚洲A∨| 亚洲国产精品久久66| 亚洲国产精品婷婷久久| 国产精品久久国产精麻豆99网站| 色综合久久久久综合体桃花网| 亚洲午夜久久久久久噜噜噜| 99蜜桃臀久久久欧美精品网站 | 久久久久国产一区二区三区|