回想ACM生涯，印象最深刻的似乎就是这两道在正式比赛中的绝杀题，两道题都是在最后一小时内憋出并成功拿下金银牌的关键题。一道是2019徐州的树上题，另一道就是这道2021银川dp题。这次来回顾一下后者的解法，前者就等以后再说吧（前面的区域，以后再来探索吧[doge]）。

题目介绍（大意）

题目

有一个长度为数组，第个数字为。需要将列表分成段，每一段的价值为：该段数字中最大值与最小值之差，即。
求如何分段能获得最高的总价值（个段价值之和）。

输入

第一行为两个空格分割的整数(1≤≤10000)和(1≤≤)，分别表示数组长度和目标段数。
第二行为个空格分割的正整数，第i个数字(1≤≤500000)为第个数字的值。

输出

所有分段方案中最高总价值。

样例输入1

1 2	5 1 2 4 5 6 3

样例输出1

样例输入2

1 2	5 2 2 4 5 6 3

样例输出2

解法1

思路

核心思路：将题目的解空间放宽

原本题意可构建dp数组，dp[i][j]表示要分为i段时前j个数字的最优解。
- 朴素算法即考虑第j个人可以和前面哪些人组成一组（最多j种情况，即[1,j]或[2,j]或…或[j,j]成一组）。设取[s,j]为一组，则分数为dp[i-1][s-1]+max(a[s],…,a[j])-min(a[s],…,a[j])。
- 故有O(n^3)的解法，转移方程为：dp[i][j] = max(dp[i-1][s-1]+max(a[s],…,a[i])-min(a[s],…,a[j]))【注意s的边界需要考虑】

将解空间放宽：将转移方程放大为：dp[i][j] = max(dp[i-1][s-1]+a[f1]-a[f2])，其中s与上述公式含义相同，f1和f2为[s,j]中的任意数字。很容易发现该公式与上述公式答案相同。

再考虑dp[i][j]和dp[i][j-1]的解空间间的差异即可简单递推。

设 {dp[x][y]}表示dp[x][y]的解空间（即dp[x][y]应当在该集合内搜索）

{dp[i][j-1]} = {
                dp[i-1][i-1]+a[i~j-1]-a[i~j-1],
                dp[i-1][i]+a[i+1~j-1]-a[i+1~j-1],
                ...
                dp[i-1][j-2]+a[j-1~j-1]-a[j-1~j-1]
                }
{dp[i][j]} = {
                dp[i-1][i-1]+a[i~j]-a[i~j],
                dp[i-1][i]+a[i+1~j]-a[i+1~j],
                ...
                dp[i-1][j-1]+a[j~j]-a[j~j]
                }

则有

{dp[i][j]}-{dp[i][j-1]} = {
                dp[i-1][i-1]+a[j]-a[i~j-1], dp[i-1][i-1]+a[i~j-1]-a[j], dp[i-1][i-1]+a[j]-a[j]
                dp[i-1][i]+a[j]-a[i+1~j-1], dp[i-1][i]+a[i+1~j-1]-a[j], dp[i-1][i]+a[j]-a[j]
                ...
                dp[i-1][j-2]+a[j]-a[j-1~j-1], dp[i-1][j-2]+a[j-1~j-1]-a[j], dp[i-1][j-2]+a[j]-a[j]
                dp[i-1][j-1]+a[j]-a[j]
                }

可以发现，dp[i-1][x]-a[x+1~~j-1] 的最大值以及 dp[i-1][x]+a[x+1~~j-1] 的最大值是可以O(1)维护的，设前者为maxDPaddA（即该数字为dp+a的最大值），后者为maxDPsubA（同理）
则转移方程为 dp[i][j] = max(dp[i][j-1],maxDPaddA-a[j],maxDPsubA+a[j])

代码

//#define ACM_LOCAL 1
#if 1

#include<bits/stdc++.h>

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
using namespace std;
typedef long long ll;

struct GlobalData {
    int N, k;
    vector<ll> dp[2];
    vector<ll> a;
    ll ans;
public:
    void init() {
        ans = 0;
    }

    void input() {
        cin >> N >> k;
        a = dp[0] = dp[1] = vector<ll>(N+1);
        for(int i=1; i<=N; i++) cin >> a[i];
    }

    void outputAns() {
        cout << ans << endl;
    }

    void preSolve() {}
} globalData;

inline void preSolve() {
    globalData.preSolve();
}

inline void input() {
    globalData.init();
    globalData.input();
}

inline void output() {
    globalData.outputAns();
}

inline void solve() {

    int nowDPno=0, lstDPno=1;

    ll mx, mn;
    mx = mn = globalData.a[1];
    for(int i=1; i<=globalData.N; i++) {
        mx = max(mx, globalData.a[i]);
        mn = min(mn, globalData.a[i]);
        globalData.dp[nowDPno][i] = mx-mn;
    }

    for(int i=2; i<=globalData.k; i++) {
        swap(nowDPno,lstDPno);
        globalData.dp[nowDPno] = vector<ll>(globalData.N+1);

        ll maxDP, maxDPaddA, maxDPsubA;
        maxDP = globalData.dp[lstDPno][i-1];
        maxDPaddA = globalData.dp[lstDPno][i-1]+globalData.a[i];
        maxDPsubA = globalData.dp[lstDPno][i-1]-globalData.a[i];

        for(int j=i+1; j<=globalData.N; j++) {
            maxDP = max(maxDP, globalData.dp[lstDPno][j-1]);
            maxDPaddA = max(maxDPaddA,maxDP+globalData.a[j]);
            maxDPsubA = max(maxDPsubA,maxDP-globalData.a[j]);
            globalData.dp[nowDPno][j] = max(globalData.dp[nowDPno][j-1],max(maxDPaddA-globalData.a[j],maxDPsubA+globalData.a[j]));
        }

    }

    globalData.ans = globalData.dp[nowDPno][globalData.N];

}

int main() {

#ifdef ACM_LOCAL
    freopen("./data/0.in", "r", stdin);
    freopen("./data/0.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    preSolve();
    int T = 1;
    // cin >> T;
    while (T--) {
        input();
        solve();
        output();
    }

    return 0;

}

#endif

解法2

思路（来自网络）

可以将每段价值转换成选择两个数相减，使得最后总和最大，那么最优必是最大值减去最小值，其实也可以看成选一个数乘上1，再选一个数乘上-1

那么设

dp[i][j][0] 表示前 i 个数分成 j 段，且第 j 段还未选择两个数，
dp[i][j][1] 表示第 j 段已经选了一个数乘上1，
dp[i][j][2] 表示第 j 段已经选了一个数乘上-1，
dp[i][j][3] 表示第 j 段已经完了两个数。

那么转移就是 O(1) 转移，具体看代码。

代码（非常有简单美）

#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int MAXN=1e4+5;
const int inf=0x3f3f3f3f;
ll dp[2][MAXN][5];
int a[MAXN];
int main()
{
    int n, x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    memset(dp,-inf,sizeof dp);
    dp[0][0][3]=0;
    int f=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){

            dp[f][j][0]=dp[f^1][j-1][3];
            dp[f][j][1]=dp[f^1][j-1][3]+a[i];
            dp[f][j][2]=dp[f^1][j-1][3]-a[i];
            dp[f][j][3]=dp[f^1][j-1][3];
            dp[f][j][0]=max(dp[f][j][0],dp[f^1][j][0]);
            dp[f][j][1]=max(dp[f][j][1],dp[f^1][j][1]);
            dp[f][j][1]=max(dp[f][j][1],dp[f^1][j][0]+a[i]);
            dp[f][j][2]=max(dp[f][j][2],dp[f^1][j][2]);
            dp[f][j][2]=max(dp[f][j][2],dp[f^1][j][0]-a[i]);
            dp[f][j][3]=max(dp[f][j][3],dp[f^1][j][3]);
            dp[f][j][3]=max(dp[f][j][3],dp[f^1][j][2]+a[i]);
            dp[f][j][3]=max(dp[f][j][3],dp[f^1][j][1]-a[i]);
        }
        f^=1;
    }
    f^=1;
    cout<<dp[f][x][3]<<endl;
}

Fre5h1nd's Blog

【ACM】2021 ICPC 银川站 - dp题