これは学びの深い DP 問題！

問題へのリンク

問題概要

長さ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。

区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$
$-10^{9} \le A_{i} \le 10^{9}$

考えたこと

まず、 $O(N^{2})$ が許されるならばよくある DP 問題だ。以下の問題と同じような DP でできる。

drken1215.hatenablog.com

chmax(dp[i], dp[j] + f(j, i))

みたいな更新式となる。 $f(j, i)$ は区間 $\lbrack j, i)$ のスコアを表す。

最大値の最大化

まさに「最大値の最大化」の考え方が使える問題でもある！

「各区間の最大値と最小値の差」は、言い換えれば「各区間から 2 値を選んだときの差の最大値」である。そう考えると、この問題は「最大値の総和の最大化」という構造を持っている。

なんらかの最大値の総和を最大化したい問題では、「何らかの最大値」のところを必ずしも「最大値」をとらなくてもよい。つまり、次の問題を考えても最適解は一緒になるのだ。

数列をいくつかの連続する区間に分割し、さらに各区間に対して次の操作を行う。

区間から 2 値を選び、それ以外の値はすべて 0 にする
2 値のうち、一方はそのままの値として、他方は -1 倍した値とする

最後に、操作後の数列の総和を求める。この総和として考えられる最大値を求めよ。

さらに言い換えれば、区間分割という文脈を捨て去り、次のように考えても同じになる。

各要素に対して 0 倍、1 倍、-1 倍のいずれかを実行する
0 倍の要素を取り除いたときに、1 倍された要素が連続してはならない
0 倍の要素を取り除いたときに、-1 倍された要素が連続してはならない

このように考えると、次の DP を考えれば良いことになる。

dp[i][j+1] ← 先頭から $i$ 個の要素を考える。1 倍した要素と -1 倍した要素の個数の差が $j$ 個であるような場合の数 ( $j = -1, 0, 1$ )

これにより、 $O(N)$ の解法となる。

別解

コストが Monge 性を満たすことから、LARSCH 法などによって DP を高速化して、 $O(N \log N)$ の計算量で求めることもできる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    // 0: - を選んだ、1: ニュートラル、2: + を選んだ
    vector dp(N+1, vector(3, -INF));
    dp[0][1] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            // 選ばない
            chmax(dp[i+1][j], dp[i][j]);
            
            // + 側で選ぶ
            if (j+1 < 3) chmax(dp[i+1][j+1], dp[i][j] + A[i]);
            
            // - 側で選ぶ
            if (j-1 >= 0) chmax(dp[i+1][j-1], dp[i][j] - A[i]);
        }
    }
    cout << dp[N][1] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CodeQUEEN 2023 決勝 E - Good Partition

問題概要

制約

考えたこと

最大値の最大化

別解

コード