• <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 - 195,  comments - 30,  trackbacks - 0

            Energy


            Status In/Out TIME Limit MEMORY Limit Submit Times Solved Users JUDGE TYPE
            stdin/stdout 3s 10240K 717 196 Standard

            Mr. Jojer is a very famous chemist. He is doing a research about behavior of a group of atoms. Atoms may have different energy and energy can be positive or negative or zero, e.g. 18 or -9. Absolute value of energy can not be more than 100. Any number of continuous atoms can form an atom-group. Energy of an atom-group is defined by the sum of energy of all the atoms in the group. All the atoms form an atom-community which is a line formed by all the atoms one by one. Energy of an atom-community is defined by the greatest energy of an atom-group that can be formed by atoms in the atom-community. The problem is, given an atom-community, to calculate its energy.

            Input

            The input contains several test cases. Each test case consists of two lines describing an atom-community. The first line of each test case contains an integer N(N<=1000000), the number of atoms in the atom-community. The second line of each test case contains N integers, separated by spaces, each representing energy of an atom, given in the order according to the atom-community. The last test case marks by N=-1, which you should not proceed.

            Output

            For each test case(atom-community description), print a single line containing the energy.

            Sample Input

            5
            8 0 6 4 -1
            -1

            Sample Output

            18


            理解題意很重要,題目的意思是說 在m個中選   連續的n個atom能量值 使其最大。
            程序中sumtemp,sum。sumtemp確定的是其左邊界,sum確定其右邊界。
            sumtemp確定左邊前n個數之和為負的最大的n,且第n個數顯然為負,然后從n+1開始選數。
            sum確定了右邊界使其最大。
            求和最大都可以用這種思路!!!!!!!!!!
            舉例
            1,2,-4,4,2,-2,1,5,-6,5,-3,8,10
            請看sumt1=1,sum=1
            sumt2=2;sum=1+2=3;
            sum3=sum2-4=-1;則sumtemp=0;sum不變。
            sum4=sumtemp+4;sum<sum4,sum=4;
            sum5=sumtemp+2;sum<sum5,sum=6
            總之sum只有在sum<sumtemp時才修改。sumtemp<0則清0.
            一維dp.
            #include"stdio.h"
            int main()
            {
             freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
             int n;
             int a;
             while(scanf("%ld",&n),n!=-1)
             { 
                  long long  sum=-0x7fffffff,sumtemp=-0x7fffffff;
               for(long i=0;i<n;i++)
               { 
                scanf("%d",&a);
                if(sumtemp>0)
               sumtemp+=a;
                else
               sumtemp=a;
                if(sumtemp>sum)
               sum=sumtemp;

               }
               printf("%lld\n",sum);

             }
             return 0;
            }

            posted on 2009-07-04 09:27 luis 閱讀(546) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃給我啟發題貪心*二分
            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久99国产综合精品| 欧美麻豆久久久久久中文| 99精品久久久久久久婷婷| 色综合久久中文字幕无码| 久久综合久久综合久久综合| 久久综合狠狠综合久久97色| 欧美熟妇另类久久久久久不卡 | 99久久精品免费国产大片| 久久福利资源国产精品999| 亚洲一区中文字幕久久| 色综合久久中文字幕综合网| 亚洲AV乱码久久精品蜜桃| 99热精品久久只有精品| 久久精品这里热有精品| 亚洲国产一成久久精品国产成人综合 | 久久亚洲高清观看| 香蕉久久影院| 日韩欧美亚洲综合久久影院d3| 久久精品国产亚洲av麻豆蜜芽| 国产精品99久久精品爆乳| 老男人久久青草av高清| 久久91这里精品国产2020| 51久久夜色精品国产| 无码人妻精品一区二区三区久久久| 久久精品国产精品亚洲艾草网美妙| 欧美777精品久久久久网| 久久亚洲AV无码精品色午夜| 国产成人久久精品麻豆一区| 精品久久久久香蕉网| 色婷婷久久综合中文久久蜜桃av| 亚洲精品乱码久久久久久蜜桃| 精品久久久久久久中文字幕| 久久久久久无码Av成人影院| 国产一区二区三区久久| 国产99久久九九精品无码| 人妻精品久久无码专区精东影业| 久久精品视频一| 久久99国产精品尤物| 亚洲狠狠婷婷综合久久久久| 久久久噜噜噜久久中文字幕色伊伊 | 久久中文字幕精品|