• <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  評(píng)論-6  文章-0  trackbacks-0
             1 //狀態(tài)轉(zhuǎn)移方程:    dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son[i]][k])    
             2 //                    以第i個(gè)城市為起點(diǎn),攻占j個(gè)城市的最大收益
             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         //問(wèn)題的關(guān)鍵在于將0作為第零個(gè)城堡,價(jià)值為零,這樣就可以實(shí)現(xiàn)大一統(tǒng)!
            48         dfs(0);
            49         printf("%d\n",dp[0][m+1]);//加入了第零個(gè)城堡,則m+1
            50     }
            51     return 0;
            52 }
            posted on 2012-07-12 22:15 Leo.W 閱讀(518) 評(píng)論(1)  編輯 收藏 引用

            評(píng)論:
            # re: hdu 1561(The more, The Better) 2012-07-23 10:58 | 77
            for(j=m+1;j>0;j--)
            為什么j 從大到小而不是從小到大?  回復(fù)  更多評(píng)論
              
            精品多毛少妇人妻AV免费久久| 狠狠色婷婷综合天天久久丁香| 色欲综合久久躁天天躁| 久久久久无码专区亚洲av| 久久免费观看视频| 亚洲第一极品精品无码久久| 欧美噜噜久久久XXX| 91精品观看91久久久久久| 狠狠色婷婷久久一区二区| 狠狠色丁香久久综合婷婷| 久久影院亚洲一区| 久久99精品久久久久久hb无码 | 久久久亚洲欧洲日产国码二区 | 精品综合久久久久久97超人 | 亚洲国产精品综合久久网络| 久久国产色AV免费观看| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 精品国产乱码久久久久久郑州公司 | 日韩精品久久久久久久电影| 91性高湖久久久久| 99久久er这里只有精品18| 亚洲精品无码久久久| 精品国产热久久久福利| aaa级精品久久久国产片| 婷婷五月深深久久精品| 亚洲欧洲精品成人久久曰影片 | 国内精品久久久久久野外| 中文字幕热久久久久久久| 色99久久久久高潮综合影院| 伊人久久精品线影院| 精品久久久久久亚洲精品| 久久天天躁狠狠躁夜夜躁2O2O| 国产一区二区久久久| 青青久久精品国产免费看| 久久精品国产72国产精福利| 国内精品伊人久久久久网站| 精品久久久久久久久久久久久久久| 久久九九亚洲精品| 青青草国产精品久久久久| 精品午夜久久福利大片| 国产成人综合久久久久久|