• <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個中選   連續(xù)的n個atom能量值 使其最大。
            程序中sumtemp,sum。sumtemp確定的是其左邊界,sum確定其右邊界。
            sumtemp確定左邊前n個數(shù)之和為負的最大的n,且第n個數(shù)顯然為負,然后從n+1開始選數(shù)。
            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)  編輯 收藏 引用 所屬分類: 動態(tài)規(guī)劃給我啟發(fā)題貪心*二分
            <2010年2月>
            31123456
            78910111213
            14151617181920
            21222324252627
            28123456
            78910111213

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久棈精品久久久久久噜噜| 亚洲AV日韩精品久久久久| 国产91久久综合| 爱做久久久久久| 欧美精品乱码99久久蜜桃| 久久综合鬼色88久久精品综合自在自线噜噜 | 亚洲中文字幕无码一久久区| 精品国产一区二区三区久久久狼| 精品多毛少妇人妻AV免费久久| 久久天天躁狠狠躁夜夜avapp | 久久久久久无码Av成人影院| 精品久久久久久无码免费| 久久九九精品99国产精品| 亚洲美日韩Av中文字幕无码久久久妻妇 | 亚洲香蕉网久久综合影视| 99精品久久久久久久婷婷| 99久久99久久精品国产片果冻| 91精品免费久久久久久久久| 色综合久久无码中文字幕| 亚洲精品无码久久毛片| 久久亚洲精品视频| 久久精品蜜芽亚洲国产AV| 欧美色综合久久久久久| 国产99久久九九精品无码| 久久精品中文无码资源站| 97精品依人久久久大香线蕉97 | 亚洲精品乱码久久久久久不卡| 久久精品国产一区| 久久久九九有精品国产| 国产高潮国产高潮久久久| 亚洲精品无码久久久影院相关影片| 久久影视国产亚洲| 久久久久国产精品嫩草影院 | 久久亚洲国产成人精品无码区| 日韩亚洲欧美久久久www综合网| 久久综合给久久狠狠97色| 亚洲精品无码久久久影院相关影片 | 久久香蕉一级毛片| 国产精品久久久99| 久久亚洲高清综合| 久久久亚洲裙底偷窥综合|