kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ yukicoder 式変形 競技プログラミング 解説 DP高速化 動的計画法 問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要与えられた長さの数列を長さ以下の個の連続部分数列に分解する. 数列のスコアをその数列の要素の和の絶対値とするとき, スコアの和の最大値を求めよ.思考の流れ問題とか制約とかから明らかにDPっぽい.すぐ思いつくのは 「前から番目まででちょうど個に分解したものの最大値」となる.以下に細かい条件を無視した遷移の式を書く.以上から, の和を求める部分を累積和を用いたとしても一回の遷移でかかるので全体でかかって間に合わない.とする. また, であることを考えると, 上記の遷移式は以下のようにかける.となるのでとが高速に計算できればいい.区間… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2020%2F07%2F19%2F233313" title="yukicoder No.1117 数列分割 - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%7BA_1%2CB_1%2CC_1%7D Hatena Blog https://hatena.blog 2020-07-19 23:33:13 rich https://kanpurin.hatenablog.com/entry/2020/07/19/233313 1.0 100%