Codeforces 484D Kindergarten(dp)

Codeforces 484D Kindergarten(dp)

題目鏈接：Codeforces 484D Kindergarten

題目大意：給定一個序列，可以分為若干段，每份的值即為該段中的最大值減掉最小值。問說所有段的總和最大為多少。

解題思路：dp[i][j]，表示第i個位置，j為0時為升序狀態，j為1是為降序狀態。根據a[i]和a[i-1]的大小可以確定升降序的轉

移。比如1 5 5 7，在第2個5的位置，即使出現了相等的情況，也會是分段的情況會更優；1 5 6 7 只有連續升序的狀態

才需要考慮說是否成段。

#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int maxn = 1e6+5;

int N, a[maxn];
ll dp[maxn][2];

int main () {
    scanf("%d%d", &N, &a[1]);

    for (int i = 2; i <= N; i++) {
        scanf("%d", &a[i]);
        if (a[i] > a[i-1]) {
            dp[i][0] = max(dp[i-1][1], dp[i-1][0] + a[i] - a[i-1]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]);
        } else {
            dp[i][1] = max(dp[i-1][0], dp[i-1][1] + a[i-1] - a[i]);
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        }
    }
    printf("%lld\n", max(dp[N][0], dp[N][1]));
    return 0;
}