首页 > 代码库 > [poj2181]jumping cows
[poj2181]jumping cows
poj 2181
Jumping Cows
Description
Farmer John‘s cows would like to jump over the moon, just like the cows in their favorite nursery rhyme. Unfortunately, cows can not jump.
The local witch doctor has mixed up P (1 <= P <= 150,000) potions to aid the cows in their quest to jump. These potions must be administered exactly in the order they were created, though some may be skipped.
Each potion has a ‘strength‘ (1 <= strength <= 500) that enhances the cows‘ jumping ability. Taking a potion during an odd time step increases the cows‘ jump; taking a potion during an even time step decreases the jump. Before taking any potions the cows‘ jumping ability is, of course, 0.
No potion can be taken twice, and once the cow has begun taking potions, one potion must be taken during each time step, starting at time 1. One or more potions may be skipped in each turn.
Determine which potions to take to get the highest jump.
Input
* Line 1: A single integer, P
* Lines 2..P+1: Each line contains a single integer that is the strength of a potion. Line 2 gives the strength of the first potion; line 3 gives the strength of the second potion; and so on.
Output
* Line 1: A single integer that is the maximum possible jump.
Sample Input
8
7
2
1
8
4
3
5
6
Sample Output
17
/翻译
农民约翰的奶牛喜欢跳过月亮，就像他们喜欢的童谣里的奶牛一样。不幸的是，奶牛不能跳跃。
The local witch doctor has mixed up P (1 <= P <= 150,000) potions to aid the cows in their quest to jump. These potions must be administered exactly in the order they were created, though some may be skipped.
当地巫医已经混合了P（1 < = < = 150000）药水，以帮助奶牛们寻求跳跃。这些药水必须按照它们创建的顺序进行管理，尽管有些可能会被跳过。
Each potion has a ‘strength‘ (1 <= strength <= 500) that enhances the cows‘ jumping ability. Taking a potion during an odd time step increases the cows‘ jump; taking a potion during an even time step decreases the jump. Before taking any potions the cows‘ jumping ability is, of course, 0.
每种药剂都有一种增强母牛跳跃能力的“力量”（1 < =力量= 500）。在一个奇数的时间段服用药水会增加母牛的跳跃；在一个偶数的时间中服用药水会降低跳跃。在服用任何药剂之前，母牛的跳跃能力当然是0
No potion can be taken twice, and once the cow has begun taking potions, one potion must be taken during each time step, starting at time 1. One or more potions may be skipped in each turn.
没有药水可以服用两次，一旦奶牛开始服用药水，每次一次必须服用一剂药水，从时间1开始。每回合可跳过一个或多个药水。
Determine which potions to take to get the highest jump.
确定哪种药剂可以获得最高的跳跃。
Emm贪心？
每次考虑当前是奇数还是偶数
奇数：尽可能大，比较是当前大还是后面的大
若当前大，取当前
偶数：尽可能小，比较是当前小还是后面的小
若当前小，去当前
1 #include<iostream>
2 #include<algorithm>
3 #include<cstdio>
4 #include<cstdlib>
5 #include<cstring>
6 #include<cmath>
7
8 using namespace std;
9
10 int ans,n,tmp,a[150101];
11 bool flag=1;
12 int read()
13 {
14 int x=0,f=1;
15 char ch=getchar();
16 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
17 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
18 return x*f;
19 }
20 int main()
21 {
22 n=read();
23 for(int i=1;i<=n;i++)a[i]=read();
24 for(int i=1;i<=n;i++)
25 {
26 if(flag==1 && a[i]>a[i+1])
27 {
28 ans+=a[i];
29 flag=0;
30 }
31 if(flag==0 && a[i]<a[i+1])
32 {
33 ans-=a[i];
34 flag=1;
35 }
36 }
37 printf("%d",ans);
38 system("pause");
39 return 0;
40 }
[poj2181]jumping cows