• <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

            問題描述

            烏拉爾大學的校長打算舉行建校80周年的晚會。大學的職員是分等級的,也就是說,職員之間的上下級關系組成了一棵以校長為根的樹。職員用1n之間的整數編號,人事處給出了每個職員的搞笑指數。為了使晚會的每個參加者都高興,校長不會同時邀請一個職員和他的頂頭上司。

            你的任務是給出一個客人的列表,使得客人的搞笑指數之和最大。

            輸入:

            第一行是一個整數n1<=n<=6000)。下面的n行每行是相應職員的搞笑指數。這個數的范圍是-128127。下面是職員的關系數。每行的格式是:<L><K>,意思是第K個職員是第L個職員的頂頭上司。輸入以0 0結束。

            輸出:

            最大的搞笑指數之和。

             

            此題個人感覺較“計算機網絡”更加簡單,遞推式更容易寫出。以d[i][0]表示第i個職員不參加,則以i為根的樹可以獲得的最大搞笑指數;以d[i][1]表示第i個職員參加,則以i為根的樹可以獲得的最大搞笑指數。

            題目意思即使i若參加,則i的兒子都不參見;若i不參加,i的兒子可參加也可不參加。這樣一來遞推式很容易寫出。

            d[i][0]=sum{ max(d[son(i)][0],d[son(i)][1]) };

            d[i][1]=fun[i]+sum{ d[son(i)][0] };

            此題中還有一個問題,就是關系樹中根的不確定。用father[i]=j表示i的父親為j,則father[i]==0的結點為根節點。(一開始沒有注意到,以為根節點是1號結點,結果樣例都過不去……)

             

             

            以下是我的代碼:

            #include<stdio.h>
            #define size 6001
            #define max(a,b) (a>b?a:b)
            typedef 
            struct NODE
            {
                
            long data;
                
            struct NODE *next;
            }
            node;
            node 
            *son[size];
            long n,root,fun[size]={0},father[size]={0},d[size][2]={0};
            node
            * newnode()
            {
                node 
            *p;
                p
            =(node*)malloc(sizeof(node));
                p
            ->data=0;
                p
            ->next=NULL;
                
            return p;
            }

            void insert(struct NODE *link,long x)
            {// x is link's Son
               node *p;
                p
            =newnode();
                p
            ->data=x;
                p
            ->next=link->next;
                link
            ->next=p;
            }

            void init()
            {
                FILE 
            *fin=fopen("year.in","r");
                
            long i,L,K;
                fscanf(fin,
            "%ld",&n);
                
            for(i=1;i<=n;i++)
                  son[i]
            =newnode();
                
            for(i=1;i<=n;i++)
                  fscanf(fin,
            "%ld",&fun[i]);
                fscanf(fin,
            "%ld%ld",&L,&K);
                
            while(L!=0||K!=0)
                
            {
                   
            // L is K's Son,K is L's Father
                   father[L]=K;
                   insert(son[K],L);
                   fscanf(fin,
            "%ld%ld",&L,&K);
                }

                fclose(fin);
            }

            void findroot()
            {
                
            long i;
                
            for(i=1;i<=n;i++)
                  
            if(father[i]==0)
                    
            break;
                root
            =i;
            }

            void dp(long k)
            {
                
            long i;
                node 
            *p;
                p
            =son[k]->next;
                
            if(p==NULL)
                  d[k][
            1]=fun[k];
                
            else
                
            {
                   
            while(p!=NULL)
                   
            {
                      dp(p
            ->data);
                      d[k][
            0]+=max(d[p->data][0],d[p->data][1]);
                      d[k][
            1]+=d[p->data][0];
                      p
            =p->next;
                   }

                   d[k][
            1]+=fun[k];
                }

            }

            void write()
            {
                FILE 
            *fout=fopen("year.out","w");
                
            long i,ans;
                ans
            =max(d[root][0],d[root][1]);
              fprintf(fout,
            "%ld\n",ans);
                fclose(fout);
            }

            int main()
            {
                init();
                findroot();
                dp(root);
                write();
            return 0;
            }

            posted on 2010-01-06 19:29 lee1r 閱讀(376) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:動態規劃
            亚洲&#228;v永久无码精品天堂久久| 久久精品一区二区国产| 一级A毛片免费观看久久精品| 污污内射久久一区二区欧美日韩| 久久人妻少妇嫩草AV蜜桃| 国产成人精品免费久久久久| 青青青青久久精品国产| 久久精品卫校国产小美女| 久久久91精品国产一区二区三区| 久久99九九国产免费看小说| 欧美牲交A欧牲交aⅴ久久| 免费一级做a爰片久久毛片潮| 久久免费的精品国产V∧| 一本色道久久综合狠狠躁篇 | 国产精品久久精品| 7777精品伊人久久久大香线蕉| 亚洲精品高清久久| 99国产欧美久久久精品蜜芽 | 欧美大香线蕉线伊人久久| 久久影院午夜理论片无码 | av无码久久久久久不卡网站| 久久久久亚洲国产| 久久综合五月丁香久久激情| 久久91亚洲人成电影网站| 伊人久久综合精品无码AV专区| 欧美精品丝袜久久久中文字幕| 97精品伊人久久久大香线蕉| MM131亚洲国产美女久久| 久久Av无码精品人妻系列| 久久久久久久久久久精品尤物 | 久久午夜免费视频| 亚洲午夜精品久久久久久app| 国产亚州精品女人久久久久久| 成人国内精品久久久久一区| 亚洲精品蜜桃久久久久久| 欧美日韩久久中文字幕| 久久精品综合网| 精品国产日韩久久亚洲| 老男人久久青草av高清| 亚洲国产成人乱码精品女人久久久不卡 | 久久婷婷五月综合97色直播|