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