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 閱讀(544)
評論(0) 編輯 收藏 引用 所屬分類:
動態規劃 、
給我啟發題 、
貪心*二分