Beautiful Array
問題はこちら
自分が気づいたところ
まず最初に，xが負の時は最小区間和を選んできてそれをx倍する．xが正の時は最大区間和を選んできてそれをx倍する．とすれば最大値が求まると考えた．ここでセグ木とかをググり始める... だが，区間和を取ってきて，その区間和のindexも取ってくるのはどのようにして実装すればいいかわからなかった．
次に，累積和を尺取りのように持てば区間和の最大・最小を検出できるのではないかと考えたが，これもACにはならず．
解説を読んで
TwitterでDPだという文面を見たので，実装は見ないで自分で書いてみた．状態の遷移は以下の通りにできると考えた．
ここでは3の状態がポイントで，一回*xをする→そのまま足すという遷移をした場合は，もう一度*xをして足すことはできない（連続した区間にのみ*xできる）ためにそれを新たに状態として持つことにした．
dp[i+1][0] := i番目をそのまま足す dp[i+1][1] := i番目を*xして足す dp[i+1][2] := 使わない（0にリセット） dp[i+1][3] := i番目までに*xをしたことがあり，i番目のものはそのまま足す
状態遷移はそれぞれを場合分けしてイテレーションを回していく．詳しくはコードを見ると早いと思う．
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(ll i = 0; i < (ll)(n); i++) const ll half_inf = ll(1e5); ll dp[3 * half_inf + 10][4]; int main() { ll n, x; cin >> n >> x; vector<ll> a(n); rep(i, n) cin >> a[i]; const int plus = 0, multi = 1, no = 2, al_multi = 3; for (int i = 0; i < n; ++i) { dp[i + 1][al_multi] = max({dp[i][multi] + a[i], dp[i][al_multi] + a[i]}); dp[i + 1][plus] = max({dp[i][plus] + a[i], dp[i][no] + a[i]}); dp[i + 1][multi] = max({dp[i][multi] + x * a[i], dp[i][no] + x * a[i], dp[i][plus] + x * a[i] }); dp[i + 1][no] = 0; } ll ans = 0; for (int i = 0; i <= n; ++i) { for (int j = 0; j < 4; ++j) { ans = max(dp[i][j], ans); } } cout << ans << endl; return 0; }
Submission #53197896 - Codeforces
こちらの解説を見るとどうやら状態数は3つでいいらしい？？（後ほど実装したい）
こちらの解法が似ているらしいので後ほど解きたい．
自分の詰まったところ
- そもそもDPという発想がコンテスト中に浮かんでこなかった．
- 遷移の歴史によって，次に行える遷移が違うがそれをどう実装するかについて．
学んだこと
- 遷移規則が複数あるが，列挙できる → DPという発想．
- 連続区間を 使う/使わない などはかなり典型例になるのでは？？
- 状態を増やすことによって遷移規則を表現できることがある．
