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; }