Patisserie ABC [AtCoder Beginner Contest 100 D]

https://beta.atcoder.jp/contests/abc100/tasks/abc100_d

前提知識

• 動的計画法

考察過程

1. まず、絶対値が面倒なので、消す方法を考える
2. 絶対値を取るということは最終的な値*(-1)をするということなので、最小であるほど良い
3. 最後に*(-1)をすると最適であるという可能性があるため、各要素について*(-1)をするかどうかの可能性がある
4. これは全探索できる
5. 最適なとり方は動的計画法で計算できるしOK

解説

https://beta.atcoder.jp/contests/abc100/submissions/2692152

公式解説では最大・最小の組み合わせで8通り全探索おこなっているが、以下の解法では最小を考える代わりにコストを*(-1)して全て最大を考えている。
　
dpは以下のdpを考える。
dp[i][j] := i番目まででj個取ったときの得点の最大値
遷移は取るか取らないかのシンプルなやつ
　
a,b,cを使って、*1か*(-1)を全探索している。
毎回しっかり配列初期化をしよう。

int N, M; ll X[1010], Y[1010], Z[1010];
ll dp[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> X[i] >> Y[i] >> Z[i];
 
    ll ans = -infl;
    rep(a, -1, 2) rep(b, -1, 2) rep(c, -1, 2) if (a) if (b) if (c) {
        rep(i, 0, N + 1) rep(j, 0, M + 1) dp[i][j] = -infl;
        dp[0][0] = 0;
        rep(i, 0, N) rep(j, 0, M + 1) {
            ll d = a * X[i] + b * Y[i] + c * Z[i];
            chmax(dp[i + 1][j], dp[i][j]);
            chmax(dp[i + 1][j + 1], dp[i][j] + d);
        }
        chmax(ans, dp[N][M]);
    }
    cout << ans << endl;
}