【51Nod - 1270】数组的最大代价（dp，思维）

题干：

数组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 ; }