• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            Tree_DP。
            要注意到樹枝上的蘋果個數有可能是0個,所以一開始構圖的時候不能用g[i][j]==0表示結點i和j之間沒有邊。
            以下是我的代碼:
            #include<iostream>
            #include
            <string.h>
            #define maxn 107
            #define max(a,b) (a>b?a:b)
            using namespace std;
            struct
            {
                
            long l,r;
            }tree[maxn];
            long n,m,g[maxn][maxn],d[maxn][maxn];
            bool used[maxn];

            void build_tree(long node)
            {
                
            bool first=true;
                used[node]
            =true;
                
            for(long i=1;i<=n;i++)
                    
            if(!used[i]&&g[node][i]!=-1)
                    {
                        
            if(first)
                        {
                            tree[node].l
            =i;
                            first
            =false;
                        }
                        
            else
                            tree[node].r
            =i;
                        build_tree(i);
                    }
            }
            long dp(long i,long j)
            {
                
            if(d[i][j]!=-1return d[i][j];
                d[i][j]
            =0;
                d[i][j]
            =max(dp(tree[i].l,j-1)+g[i][tree[i].l],dp(tree[i].r,j-1)+g[i][tree[i].r]);
                
            for(long k=0;j-k-2>=0;k++)
                    d[i][j]
            =max(d[i][j],dp(tree[i].l,k)+dp(tree[i].r,j-k-2)+g[i][tree[i].l]+g[i][tree[i].r]);
                
            return d[i][j];
            }
            int main()
            {
                
            /*
                freopen("data.in","r",stdin);
                freopen("data.out","w",stdout);
                //
            */
                cin
            >>n>>m;
                memset(g,
            -1,sizeof(g));
                
            for(long i=1;i<=n-1;i++)
                {
                    
            long a,b,w;
                    cin
            >>a>>b>>w;
                    g[a][b]
            =g[b][a]=w;
                }
                
            //  Input
                memset(tree,0,sizeof(tree));
                memset(used,
            false,sizeof(used));
                build_tree(
            1);
                
            //  Build Tree
                
                
            /*
                for(long i=1;i<=n;i++)
                    cout<<tree[i].l<<" "<<tree[i].r<<endl;
                //
            */
                
                
            for(long i=0;i<=n;i++)
                    
            for(long j=0;j<=n;j++)
                        d[i][j]
            =-1;
                
            for(long i=0;i<=n;i++)
                    d[
            0][i]=d[i][0]=0;
                
            //  Init
                cout<<dp(1,m)<<endl;
                
            //  Dp & Output
            return 0;
            }


            posted on 2010-09-12 13:19 lee1r 閱讀(255) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:動態規劃
            欧美喷潮久久久XXXXx| 久久久久久噜噜精品免费直播| 久久久高清免费视频| 伊人久久大香线蕉亚洲| 麻豆AV一区二区三区久久| 久久婷婷综合中文字幕| 香蕉99久久国产综合精品宅男自| 亚洲精品国精品久久99热| 久久国产亚洲精品无码| 国内精品久久久久久中文字幕| 久久精品极品盛宴观看| 精品国产一区二区三区久久| 国产69精品久久久久APP下载| 国产人久久人人人人爽| 国产69精品久久久久APP下载| 欧美伊香蕉久久综合类网站| 国产精品久久久久久五月尺| 777久久精品一区二区三区无码 | 久久综合久久综合九色| 久久人与动人物a级毛片| 99热精品久久只有精品| 久久精品国产亚洲av麻豆小说| 精品久久久久久久久久中文字幕| 久久66热人妻偷产精品9| 一日本道伊人久久综合影| 狠狠综合久久综合中文88 | 久久国产精品久久精品国产| 欧美国产成人久久精品| 日本高清无卡码一区二区久久| 久久精品国产99国产电影网| 久久久av波多野一区二区| 久久久久久综合网天天| 伊人久久大香线蕉综合热线| 久久久久女教师免费一区| 久久91精品久久91综合| 国产精品久久成人影院| 国产精品久久国产精品99盘| 狠狠88综合久久久久综合网 | 久久精品日日躁夜夜躁欧美| 亚洲精品tv久久久久久久久久| 无码任你躁久久久久久|