題干：

數組A包含N個元素A1, A2......AN。數組B包含N個元素B1, B2......BN。并且數組A中的每一個元素Ai，都滿足1 <= Ai <= Bi。數組A的代價定義如下：

?

?

（公式表示所有兩個相鄰元素的差的絕對值之和）

給出數組B，計算可能的最大代價S。

Input

第1行：1個數N，表示數組的長度(1 <= N <= 50000)。 第2 - N+1行：每行1個數，對應數組元素Bi(1 <= Bi <= 10000)。

Output

輸出最大代價S。

Sample Input

5 10 1 10 1 10

Sample Output

36

解題報告：

? 如果直接按照題意定義dp[i][j]代表截止到第i個數，且第i-1個數選的是j，的最大代價。這樣轉移的話顯然就炸了。我們通過分析問題不難發現，因為代價函數是絕對值的形式，那么要想讓這個代價最大，很顯然要么取最小值，要么取b[i]，所以直接dp[n][2]其實就可以解決這個問題了。這樣就大大縮小了狀態個數，也方便了求解。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,a[MAX]; ll dp[MAX][2]; int main() {cin >> n;for(int i = 1; i<=n; i++) {scanf("%d",a+i);if(i == 1) continue;dp[i][0] = max(dp[i-1][0],dp[i-1][1] + abs(a[i-1]-1));dp[i][1] = max(dp[i-1][0] + abs(a[i]-1),dp[i-1][1] + abs(a[i]-a[i-1]));}cout << max(dp[n][0],dp[n][1]) << endl;return 0 ; }

?

總結

以上是生活随笔為你收集整理的【51Nod - 1270】数组的最大代价（dp，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。