つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック！！！！

問題へのリンク

問題概要

長さ $N$ の 2 つの数列 $a_{1}, a_{2}, \dots, a_{N}$ と $b_{1}, b_{2}, \dots, b_{N}$ が与えられる。今、互いに disjoint な区間群

$\lbrack l_{1}, r_{1} \rbrack, \lbrack l_{2}, r_{2} \rbrack, \dots, \lbrack l_{k}, r_{k} \rbrack$

をとる ( $k$ は自由)。ただし、区間の長さの総和がちょうど $K$ となるようにする必要がある。つまり、

$\displaystyle \sum_{i=1}^{k} (r_{i} - l_{i} + 1) = K$

を満たす必要がある。そのような区間群に対して、

$\displaystyle \sum_{i=1}^{k} (|a_{l_{i}} - b_{r_{i}}| + |a_{r_{i}} - b_{l_{i}}|)$

の値の最大値を求めよ。

制約

$1 \le K \le N \le 3000$

解法

区間を分割していく、いつもの DP。単純にやると $O(N^{2}K)$ の計算量となるやつ。しかし「最大値の最大化」典型が使える。

$|a_{l} - b_{r}| + |a_{r} - b_{l}|$
$= \max((a_{l}+b_{l})-(a_{r}+b_{r}), (a_{l}-b_{l})-(a_{r}-b_{r}), (-a_{l}+b_{l})-(-a_{r}+b_{r}), (-a_{l}-b_{l})-(-a_{r}-b_{r} ) )$

が成り立つことに注目する。このことから、次のような DP が組める

先頭から $i$ 個の要素のみを考える。その中ですでに選んだ区間の長さの総和が $k$ (右端が閉じていない場合も含み、その場合は右端を閉じない限りは 1 ずつ増えていく) である場合について、

dp[i][k][0] ← 最後の区間の右端が閉じている状態
dp[i][k][1] ← 最後の区間の右端が閉じておらず、左端が $a_{i} + b_{i}$ である状態
dp[i][k][2] ← 最後の区間の右端が閉じておらず、左端が $a_{i} - b_{i}$ である状態
dp[i][k][3] ← 最後の区間の右端が閉じておらず、左端が $-a_{i} + b_{i}$ である状態
dp[i][k][4] ← 最後の区間の右端が閉じておらず、左端が $-a_{i} - b_{i}$ である状態

についての、スコアの最大値

こうすることで、DP は直前の状態との比較のみで実現できるようになり、計算量は $O(NK)$ となる。

コード

#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; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;

void solve() {
    int N, K;
    cin >> N >> K;
    vector<long long> a(N), b(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];
    
    // 0: non, 1: ++, 2: +-, 3: -+, 4: --
    vector dp(K+2, vector(5, -INF));
    dp[0][0] = 0;
    for (int r = 0; r < N; ++r) {
        vector nex(K+2, vector(5, -INF));
        for (int k = 0; k <= K; ++k) {
            // 0 -> 0
            chmax(nex[k][0], dp[k][0]);
            chmax(nex[k+1][0], dp[k][0] + abs(a[r] - b[r]) * 2);
            
            // 0 -> 1, 2, 3, 4
            chmax(nex[k+1][1], dp[k][0] + a[r] + b[r]);
            chmax(nex[k+1][2], dp[k][0] + a[r] - b[r]);
            chmax(nex[k+1][3], dp[k][0] - a[r] + b[r]);
            chmax(nex[k+1][4], dp[k][0] - a[r] - b[r]);
            
            // 1, 2, 3, 4 keep
            for (int p = 1; p <= 4; ++p) chmax(nex[k+1][p], dp[k][p]);
            
            // 1, 2, 3, 4 -> 0
            chmax(nex[k+1][0], dp[k][1] - a[r] - b[r]);
            chmax(nex[k+1][0], dp[k][2] - a[r] + b[r]);
            chmax(nex[k+1][0], dp[k][3] + a[r] - b[r]);
            chmax(nex[k+1][0], dp[k][4] + a[r] + b[r]);
        }
        swap(dp, nex);
    }
    cout << dp[K][0] << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}

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

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

Codeforces Round 892 (Div. 2) E. Maximum Monogonosity (R??00)

問題概要

制約

解法

コード