Jumping Cows（谢庆皇）答题报告

Jumping Cows（谢庆皇）解题报告

大意：一群牛想要跳到月亮上面去，但是他们现在跳的能力为零。现在给你一些药水，能改变他们跳的能力。不能改变药水的顺序。当跳奇数跳的时候，就增加，当跳偶数跳的时候就减少。药水是可以跳过不喝的。

先开始想的是把最大值最小值用一个二维数组表示，结果怎么想都想不出来，主要还是想到了要记步数，后来才去看解题报告，上面说什么开个二维数组，可以表示奇数步和偶数步。

选与不选这个问题，在代码里面说明吧~~~

#define MAX  150005
int dp[MAX][2],a[MAX];
int max(int x,int y)
{
	if(x>y)
		return x;
	else
		return y;
}
int main(void)
{
    int n,i,j;
	while(scanf("%d",&n)!=EOF)
	{
        for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		memset(dp,0,sizeof(dp));
		memset(dp,0,sizeof(dp));
		dp[2][0]=max(0,a[1]-a[2]);
		dp[2][1]=max(a[1],a[2]);
		for(i=3;i<=n;i++)
		{
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]-a[i]);//前面就是不选的状态     
		    dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i]);  
		}
		printf("%d\n",max(dp[n][0],dp[n][1]));
	}
	return 0;
}

还可以不用开数组：当dp[i][0]存那一个点的权值时，状态转移方程为奇数：dp[i][1]=max{dp[i-1][1],dp[i-1][2]-dp[i][0]};偶数：dp[i][2]=max{dp[i-1][2],dp[i-1][1]+dp[i][0]};
　　以上方程可以发现，每种状态只跟他的前一种状态有关，所以可以用状态压缩，并可以使用在线算法，即每读入一个数以后做完运算就不要了，这样只要3个变量就可以完成任务。
　　最后提醒下大家要使用O(n)的算法，因为输入的N最多是1500000，有人外一不小心用了O(n^2)的算法，哪怕第2层循环只做一次，也是要TLE的。

#include<stdio.h>
#include<string.h>
int maxj=0,maxo=0,a;
int main()
{
    int t,i,j;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&a);
        if(maxj+a>maxo)
			maxo=maxj+a;
		if(maxo-a>maxj)
			maxj=maxo-a;
	}
	if(maxj>maxo)
		printf("%d\n",maxj);
	else
		printf("%d\n",maxo);
	return 0;

点击打开链接http://acm.fjut.edu.cn/JudgeOnline/showproblem?problem_id=1053

Jumping Cows（谢庆皇）答题报告

相关推荐