【分析】想到DP就简单了,用dp[i][j]表示前i个元素中第i个元素取最大或者最小值时的最大价值。
转移方程:
dp[i][0] = max(dp[i-1][0]+abs(1-1),dp[i-1][1]+abs(1-a[i-1]));
dp[i][1] = max(dp[i-1][0]+abs(a[i]-1),dp[i-1][1]+abs(a[i]-a[i-1]));
复杂度O(N)
【AC CODE】93ms
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 50000+10; int a[MAXN],dp[MAXN][2]; int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int n; scanf("%d", &n); rep(i,0,n) scanf("%d", &a[i]); rep(i,1,n) { dp[i][0] = max(dp[i-1][0]+abs(1-1),dp[i-1][1]+abs(1-a[i-1])); dp[i][1] = max(dp[i-1][0]+abs(a[i]-1),dp[i-1][1]+abs(a[i]-a[i-1])); } printf("%d\n", max(dp[n-1][0],dp[n-1][1])); return 0; }