題目鏈接：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 }
?
)
