大意：一群牛想要跳到月亮上面去，但是他们现在跳的能力为零。现在给你一些药水，能改变他们跳的能力。不能改变药水的顺序。当跳奇数跳的时候，就增加，当跳偶数跳的时候就减少。药水是可以跳过不喝的。
先开始想的是把最大值最小值用一个二维数组表示，结果怎么想都想不出来，主要还是想到了要记步数，后来才去看解题报告，上面说什么开个二维数组，可以表示奇数步和偶数步。
选与不选这个问题，在代码里面说明吧~~~
#include
#include
#include
#include
#include
#define MAXN 150000+10
int a[MAXN];
int dp[MAXN][2];
int max(int a,int b)
{ if(a>b) return a; else return b;
} int main(void)
{ int P; while(scanf("%d",&P)==1) { memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); int i; for(i=1;i<=P;i++) scanf("%d",&a[i]); dp[2][0]=max(0,a[1]-a[2]);//这里的处理挺巧的，我怎么就想不到…… dp[2][1]=max(a[1],a[2]); for(i=3;i<=P;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[P][0],dp[P][1])); }
}
Tags:
延伸阅读
最新评论