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

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久亚洲精品国产精品婷婷| 一本色道久久99一综合| 久久99精品国产麻豆不卡| 久久99国产精品成人欧美| 久久天天躁狠狠躁夜夜2020一| 久久强奷乱码老熟女网站| 国产精品久久久久国产A级| Xx性欧美肥妇精品久久久久久| 99蜜桃臀久久久欧美精品网站 | 久久免费的精品国产V∧| 久久久一本精品99久久精品88| 九九99精品久久久久久| 91性高湖久久久久| 精品久久久久久国产潘金莲 | 99久久精品久久久久久清纯| 国产成人精品久久| 国产99精品久久| 久久线看观看精品香蕉国产| 精品午夜久久福利大片| 久久精品国产只有精品2020| 国产午夜久久影院| 看全色黄大色大片免费久久久| 品成人欧美大片久久国产欧美...| 久久久久久av无码免费看大片| 无码人妻少妇久久中文字幕| 久久天天躁狠狠躁夜夜96流白浆| 蜜臀久久99精品久久久久久小说| 国产精品女同久久久久电影院| 久久久综合九色合综国产| 久久久久久精品免费看SSS| 国产福利电影一区二区三区,免费久久久久久久精| 久久亚洲国产精品一区二区| 亚洲中文字幕伊人久久无码| 国产免费福利体检区久久 | 狠狠色综合网站久久久久久久| 久久久久亚洲精品天堂| 亚洲AV无码一区东京热久久| 7777精品伊人久久久大香线蕉| 中文精品久久久久国产网址| 久久99精品久久久久久久不卡| 人人妻久久人人澡人人爽人人精品|