青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(556) 評論(0)  編輯 收藏 引用 所屬分類: 動態(tài)規(guī)劃 、給我啟發(fā)題 、貪心*二分
<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用鏈接

留言簿(3)

隨筆分類

隨筆檔案

文章分類

文章檔案

友情鏈接

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久国产精品网站| 亚洲成人中文| 一区二区三区国产盗摄| 农夫在线精品视频免费观看| 欧美在线观看网站| 1000部精品久久久久久久久| 欧美激情在线免费观看| 欧美日韩视频在线| 午夜精品999| 久久精品国产999大香线蕉| **欧美日韩vr在线| 日韩小视频在线观看| 国产精品久久久免费| 欧美在线免费观看| 久色成人在线| 在线视频你懂得一区| 亚洲欧美在线网| 精品88久久久久88久久久| 亚洲国产小视频在线观看| 欧美sm极限捆绑bd| 校园激情久久| 久热精品视频在线观看一区| 亚洲视频在线观看三级| 久久精品国产免费观看| 99热精品在线| 久久五月天婷婷| 亚洲自拍三区| 麻豆av福利av久久av| 亚洲免费网址| 毛片基地黄久久久久久天堂 | 久久精品成人欧美大片古装| 亚洲黑丝在线| 午夜伦欧美伦电影理论片| 亚洲黄网站黄| 久久电影一区| 亚洲欧美日韩精品一区二区| 久久婷婷一区| 久久成人免费日本黄色| 欧美伦理影院| 欧美国产一区二区| 国产一区二区三区av电影| aa级大片欧美三级| 亚洲国产精品一区二区第一页| 亚洲免费网址| 亚洲午夜一区二区三区| 蜜桃av综合| 久久综合给合久久狠狠狠97色69| 欧美色123| 亚洲欧洲精品一区二区三区波多野1战4| 国产欧美精品| 亚洲无线视频| 亚洲少妇最新在线视频| 欧美福利视频在线| 免费一级欧美片在线观看| 国产亚洲精品自拍| 午夜精品久久久久久| 亚洲一区免费观看| 欧美午夜电影在线| 日韩亚洲欧美在线观看| 亚洲六月丁香色婷婷综合久久| 久久只精品国产| 欧美不卡福利| 亚洲第一黄网| 久久综合九色欧美综合狠狠| 久久天天躁狠狠躁夜夜av| 国产午夜精品美女视频明星a级 | 久久精品国产久精国产思思| 国产精品黄色在线观看| 一区二区三区精品在线| 亚洲一区二区免费| 国产精品普通话对白| 亚洲欧美伊人| 狼狼综合久久久久综合网 | 国产亚洲福利社区一区| 欧美一区激情视频在线观看| 久久久www成人免费无遮挡大片| 国产精品一区二区三区观看| 性欧美videos另类喷潮| 久久久久久网| 亚洲国产影院| 欧美午夜精品理论片a级大开眼界| 一区二区精品| 久久国产一区| 在线成人免费观看| 欧美韩国在线| 亚洲国产精品久久久久秋霞影院 | 91久久中文| 亚洲一区二区三区中文字幕| 国产精品视频免费一区| 久久精品人人做人人爽电影蜜月| 美女主播视频一区| 日韩午夜三级在线| 国产精品久久久久久久久久免费| 午夜久久黄色| 亚洲缚视频在线观看| 亚洲欧美日韩在线一区| 激情小说亚洲一区| 欧美日韩1234| 欧美在线视频观看| 91久久午夜| 久久精品夜色噜噜亚洲a∨| 亚洲欧洲精品一区| 国产精品精品视频| 老司机精品视频网站| 亚洲最快最全在线视频| 久久影院午夜片一区| 一区二区免费在线播放| 国产综合久久久久久| 欧美日韩 国产精品| 久久国产欧美精品| 一区二区激情小说| 亚洲国产精品毛片| 久久嫩草精品久久久久| 亚洲午夜精品久久| 91久久久久久久久久久久久| 国产精品亚洲аv天堂网| 欧美国产一区二区在线观看| 欧美在线视频导航| 亚洲男人的天堂在线| 亚洲欧洲日韩女同| 欧美电影免费| 久久最新视频| 久久精品国产精品亚洲精品| 亚洲在线观看免费视频| 亚洲精品永久免费精品| 黄色成人91| 国产日韩精品一区| 国产精品美女久久久久av超清| 欧美国产高清| 免费不卡在线观看av| 久久精品一本久久99精品| 亚洲一区尤物| 亚洲视频一区二区免费在线观看| 亚洲高清在线播放| 欧美国产成人精品| 久久亚洲欧洲| 久久综合一区二区| 久久视频在线看| 久久综合导航| 免费日韩精品中文字幕视频在线| 久久久av水蜜桃| 另类av导航| 免费看的黄色欧美网站| 久久久亚洲成人| 免费看成人av| 亚洲国产日韩欧美一区二区三区| 欧美大片18| 亚洲第一级黄色片| 91久久综合亚洲鲁鲁五月天| 亚洲欧洲综合另类在线| 亚洲精品视频二区| 99视频精品| 亚洲图片你懂的| 性欧美xxxx视频在线观看| 香蕉尹人综合在线观看| 欧美在现视频| 蜜臀va亚洲va欧美va天堂| 欧美大色视频| 久久综合久色欧美综合狠狠| 麻豆精品视频在线| 亚洲日本免费| 亚洲伊人网站| 久久久亚洲欧洲日产国码αv| 麻豆成人综合网| 欧美日韩精品在线视频| 国产精品久久午夜夜伦鲁鲁| 国产三区二区一区久久| 亚洲国产三级网| 亚洲男人第一av网站| 久久久久久久高潮| 91久久久久久| 亚洲男女毛片无遮挡| 免费久久精品视频| 国产精品久久久久久久久久久久久| 国产亚洲精品久久久| 亚洲精品美女久久7777777| 亚洲一区二区三区精品在线观看 | 欧美va亚洲va香蕉在线| 一区二区三区高清在线| 欧美在线观看天堂一区二区三区| 欧美精品18+| 国语自产精品视频在线看一大j8| 日韩视频免费观看高清在线视频 | 亚洲人成网站色ww在线| 欧美一区二区免费观在线| 欧美刺激性大交免费视频| 亚洲视频高清| 免费在线日韩av| 国产午夜亚洲精品理论片色戒| 亚洲人成亚洲人成在线观看| 香蕉久久精品日日躁夜夜躁| 亚洲高清二区| 欧美在线播放高清精品| 欧美日韩综合网| 亚洲黄网站在线观看| 久久欧美中文字幕| 亚洲自拍电影| 欧美特黄一级| 日韩一级精品| 欧美福利小视频|