51nod 1270 – 数组的最大代价(简单DP)

51nod1270

【分析】想到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;
}