[51nod1270] 数组的最大代价(简单dp)

解题关键：先由贪心的思想得出任何一个位置只能取1或者a[i],然后dp即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 50002
int a[maxn],dp[maxn][2];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    dp[0][0]=dp[0][1]=0;
    for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+abs(a[i-1]-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",max(dp[n-1][0],dp[n-1][1]));
    return 0;
}