• <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 閱讀(547) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃給我啟發題貪心*二分
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产精品久久久久婷婷老年| 久久精品无码一区二区三区免费| 伊人久久精品无码av一区| 午夜精品久久久久成人| 久久水蜜桃亚洲av无码精品麻豆| 91精品日韩人妻无码久久不卡| 亚洲午夜无码AV毛片久久| 亚洲午夜久久久久久久久电影网| 久久精品欧美日韩精品| 久久久久亚洲爆乳少妇无| 99久久精品免费看国产一区二区三区 | 色综合久久无码五十路人妻| 久久av无码专区亚洲av桃花岛| 久久不见久久见免费影院www日本| 三级三级久久三级久久| 91精品免费久久久久久久久| 久久影院综合精品| 久久久午夜精品福利内容| 99久久无码一区人妻| 久久天天躁狠狠躁夜夜avapp| 亚洲欧洲精品成人久久奇米网| 精品久久久久久中文字幕| 看久久久久久a级毛片| 99久久国产综合精品女同图片 | 久久免费视频1| 久久精品不卡| 久久人妻少妇嫩草AV无码蜜桃| 一级做a爰片久久毛片16| 国产亚洲欧美精品久久久| 一本一本久久A久久综合精品| 午夜精品久久久久久| 久久久久香蕉视频| 久久久久亚洲AV无码专区桃色| 精品999久久久久久中文字幕| 九九久久自然熟的香蕉图片| 亚洲国产欧美国产综合久久| 亚洲中文字幕无码久久2017| 婷婷久久香蕉五月综合加勒比| 亚洲精品美女久久久久99| 老色鬼久久亚洲AV综合| 精品久久久久久无码中文字幕一区 |