【基础DP】51nod 1270 数组的最大代价

Bryce1010模板
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1270

---

思路：
由于每次取值要么取1，要么取最大值，都是取极值，所以总的状态为2^n
以当前的到第几位为阶段，当前取最大值还是最小值为状态，dp[i][0] 取1， dp[i][1]取bi
一遍O(n)DP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
const int MAXN=5e4+10;

int dp[MAXN][3];
int b[MAXN];
int n;


int main()
{   
    cin>>n;
    dp[1][0]=dp[1][1]=0;
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=2;i<=n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+b[i-1]-1);
        dp[i][1]=max(dp[i-1][0]+b[i]-1,dp[i-1][1]+abs(b[i]-b[i-1]));
    }
    cout<<max(dp[n][0],dp[n][1])<<endl;
    return 0;

}