ひらめの日常

プログラミングと読書と

dp

ABC130-E Common Subsequence (500)

Common Subsequence 問題はこちら atcoder.jp この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。 LCS 最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。 s: abcd t: acfed …

Educational Codeforces Round 63 D. Beautiful Array

Beautiful Array 問題はこちら codeforces.com 自分が気づいたところ まず最初に,xが負の時は最小区間和を選んできてそれをx倍する.xが正の時は最大区間和を選んできてそれをx倍する.とすれば最大値が求まると考えた.ここでセグ木とかをググり始める... …

ABC095-D Static Sushi (500)

Static Sushi 問題はこちら atcoder.jp 自分が気づいたところ 最大でも反対方向に向きを変える動きは一回だけなので,反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた. これだと,計算量は反転する場所が ,反転後の最大値探索が…