POJ2182总结

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

我的代码

原先准备用最朴素的动态规划做：

	for (int i=1;i<=p;i++){
		for (int j=1;j<=i;j++){
			if (j%2==1){
				dp[j]=dp[j]>dp[j-1]+potions[i]?dp[j]:dp[j-1]+potions[i];
			}else{
				dp[j]=dp[j]>dp[j-1]-potions[i]?dp[j]:dp[j-1]-potions[i];
			}
			if (dp[j]>ans) ans=dp[j];
		}
	}

有一种背包问题的意思。但是，算了一下N^2的复杂度必然过不掉，只能另外想办法。

我最后想到一个O(N)的算法，就是奇数次喝的药是从可选的第一个魔药开始上升子段的最后一个元素，偶数次是下降子段的最后一个元素。证明不是很复杂，画个图可以说明一下，就以题目中给的数据为例：

第一次魔药喝的是从7开始的上升子段的最后一个，只能是7；第二次喝的从2开始的下降子段的最后一个，即1；第三次是8；第四次是3；第五次是6。

对于奇数个魔药：如果不选上升段的最后一个，不妨设在长为l的上升子段中选第k个，那么第k+1个到第l个如果被选上了，那一定是在偶数次喝药，这两次的结果必然是负数，不如直接喝上升段的最后一个大；如果第k+1个到第l个不被选上，那么无论之后的偶数个选什么，这奇数个的取值都没有选第l个的大。

对于偶数个的魔药同理。

最后答案就是累加选中的药水，不过要处理一下，只喝奇数次药，即如果选中了偶数次药，最后一次不能选上。

#include<stdio.h>

int p,now=1,base=1,ans=0;
int potions[150010];
int dp[150010];
int main()
{		
	scanf("%d",&p);
	for (int i=1;i<=p;i++){
		scanf("%d",&potions[i]);
	}
	dp[1]=potions[1];
	for (int i=2;i<=p;i++){
		if (now%2==1){
			if (potions[i]>=dp[now]) {
				dp[now]=potions[i];
			}else{
				dp[++now]=potions[i];
			}
		}else{
			if(potions[i]<=dp[now]){
				dp[now]=potions[i];
			}else{
				dp[++now]=potions[i];
			}
		}
	}
	now=now+(now%2-1);
	for (int i=1;i<=now;i++){
		ans+=base*dp[i];
		base=base*(-1);
	}
//	for (int i=1;i<=p;i++){
//		for (int j=1;j<=i;j++){
//			if (j%2==1){
//				dp[j]=dp[j]>dp[j-1]+potions[i]?dp[j]:dp[j-1]+potions[i];
//			}else{
//				dp[j]=dp[j]>dp[j-1]-potions[i]?dp[j]:dp[j-1]-potions[i];
//			}
//			if (dp[j]>ans) ans=dp[j];
//		}
//	}
	printf("%d\n",ans);
	return 0;
}

反思

我发现这题其实是可以直接dp的。。。