EZOJ #227

传送门

分析

我们发现第一段数和最后一段数对答案的贡献系数为1/-1，其余为0/2/-2

而且对于相邻两段不能系数均非0

于是可以dp

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const int inf = 1e9+;

int dp[][][];

int main(){

    int n,m,i,j,k,x;

    scanf("%d%d",&n,&m);

    for(i=;i<=m;i++)

      for(j=;j<;j++)

        dp[][i][j]=-inf;

    for(i=;i<=n;i++){

      scanf("%d",&x);

      for(j=;j<=m;j++){

          k=-((j==)||(j==m));

          dp[i][j][]=max(dp[i-][j][],dp[i-][j-][])-k*x;

          dp[i][j][]=max(dp[i-][j][],dp[i][j][]);

          dp[i][j][]=max(dp[i-][j][],dp[i-][j-][])+k*x;

          dp[i][j][]=max(dp[i-][j][],dp[i][j][]);

          if(k>){

            dp[i][j][]=max(dp[i][j][],dp[i-][j-][]);

            dp[i][j][]=max(dp[i][j][],dp[i-][j-][]);

          }

      }

    }

    cout<<max(dp[n][m][],dp[n][m][]);

    return ;

}