51nod1270(dp)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1270

题意：中文题诶～

思路：dp

s=abs(a1-a0)+abs(a2-a1)....

要使s尽量大，需要让abs(ai-ai-1)尽量大，那么可以让其中一个尽量小，一个尽量大。1<=ai<=bi，所以可以令其中一个为1，一个为bi/bi-1(通过样列大概也能看出那么一点点来)。

那么接下来就是一个简单的dp过程呐.....

用dp[i][0]存储当到第 i 个元素为止前元素选1的最大s，dp[i][1]存储当前选b[i]的最大s，那么状态转移方程为：

　　 dp[i][0]=max(dp[i-1][0], dp[i-1][1]+abs(a[i-1]-1));//当前元素选1
dp[i][1]=max(dp[i-1][0]+abs(a[i]-1), dp[i-1][1]+abs(a[i]-a[i-1]));//当前元素选a[i]

代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAXN=5e4+10;
 7 int a[MAXN], dp[MAXN][2];//dp[i][0]存储当前元素选1的最大s,dp[i][1]存储当前选b[i]的最大s
 8 
 9 int main(void){
10     int n;
11     scanf("%d", &n);
12     for(int i=0; i<n; i++){
13         scanf("%d", &a[i]);
14     }
15     for(int i=1; i<n; i++){
16         dp[i][0]=max(dp[i-1][0], dp[i-1][1]+abs(a[i-1]-1));//当前元素选1
17         dp[i][1]=max(dp[i-1][0]+abs(a[i]-1), dp[i-1][1]+abs(a[i]-a[i-1]));//当前元素选a[i]
18     }
19     cout << max(dp[n-1][0], dp[n-1][1]) << endl;
20     return 0;
21 }

View Code