正文
Kindergarten CodeForces - 484D (贪心,好题)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
大意: 给定序列, 求划分为若干段, 使得总贡献最大, 每段的贡献为max-min
可以发现最优解一定是连续一段递增或递减, 然后dp即可.
#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;const int N = 1e6+10;
int n, a[N];
ll dp[2][N];
int main() {
scanf("%d", &n);
REP(i,1,n) scanf("%d", a+i);
REP(i,2,n) {
dp[a[i]>a[i-1]][i] = dp[a[i]>a[i-1]][i-1]+abs(a[i]-a[i-1]);
ll t = max(dp[0][i-1],dp[1][i-1]);
dp[0][i] = max(dp[0][i],t);
dp[1][i] = max(dp[1][i],t);
}
printf("%lld\n", max(dp[1][n],dp[0][n]));
}
