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

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            香蕉久久永久视频| 久久综合噜噜激激的五月天| 精品综合久久久久久97超人| 9久久9久久精品| 人妻少妇精品久久| 亚洲人成精品久久久久| 精品久久人妻av中文字幕| 久久精品国产精品亚洲艾草网美妙| 中文精品99久久国产 | 99久久99久久精品国产| 国内精品久久久久影院网站| 国产A三级久久精品| 久久久国产精品网站| 2021国产精品久久精品| 国产精品99久久久久久www| 免费无码国产欧美久久18| 国产 亚洲 欧美 另类 久久| 久久久久久国产精品美女| 日本精品一区二区久久久| 久久亚洲精品视频| 久久久久人妻一区精品性色av| 久久亚洲2019中文字幕| 狠狠精品干练久久久无码中文字幕| 久久综合给合久久狠狠狠97色| 亚洲成av人片不卡无码久久| 久久ZYZ资源站无码中文动漫| 久久久久久久免费视频| 人妻中文久久久久| 久久精品无码免费不卡| 国产福利电影一区二区三区久久久久成人精品综合 | 2020国产成人久久精品| 久久无码国产| 亚洲国产高清精品线久久| 久久久久亚洲AV无码去区首| 精品久久久久久久中文字幕| 99久久国产主播综合精品| 中文字幕久久欲求不满| 国产精品永久久久久久久久久| 国产高潮国产高潮久久久91 | 久久久久亚洲精品男人的天堂 | A狠狠久久蜜臀婷色中文网|