{"provider_url":"https://hatena.blog","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F02%2F08%2F182047\" title=\"Codeforces Round #219 (Div. 1) C. Watching Fireworks is Fun - mayoko\u2019s diary\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","title":"Codeforces Round #219 (Div. 1) C. Watching Fireworks is Fun","image_url":null,"published":"2016-02-08 18:20:47","description":"\u554f\u984c codeforces.com \u89e3\u6cd5 \u666e\u901a\u306b dp \u3057\u3088\u3046\u3068\u8003\u3048\u308b\u3068, dp[m][n] = (m \u500b\u76ee\u306e\u82b1\u706b\u306e\u6642\u5ea7\u6a19 n \u306b\u3044\u308b\u3088\u3046\u306a\u5834\u5408\u3067, \u559c\u3073\u5ea6\u306e max \u5024) \u3068\u3044\u3046\u306e\u304c\u8003\u3048\u3089\u308c\u3066, \u3053\u308c\u306f dp[m][n] = (dp[m][n-diff], dp[m][n-diff+1], ..., dp[m][n+diff] \u306e\u6700\u5c0f\u5024) + abs(A[m]-n) \u3068\u66f8\u3051\u307e\u3059\u3002\u6700\u5c0f\u5024\u306f\u533a\u9593\u7684\u306b\u306a\u3063\u3066\u3044\u308b\u306e\u3067, segment tree \u3067\u5927\u52dd\u5229, \u304b\u3068\u601d\u3063\u305f\u3093\u3067\u3059\u304c n*m \u306e\u6642\u70b9\u3067\u7d50\u69cb\u304d\u3064\u3044\u306e\u3067 O(nm log n) \u3060\u3068\u9593\u306b\u5408\u3044\u307e\u305b\u3093\u3002\u3068\u3044\u3046\u3053\u3068\u3067, O(nm) \u306b\u3059\u308b\u3053\u3068\u3092\u8003\u3048\u308b\u3093\u2026","author_url":"https://blog.hatena.ne.jp/mayokoex/","version":"1.0","width":"100%","author_name":"mayokoex","blog_url":"https://mayokoex.hatenablog.com/","height":"190","categories":["CodeForces"],"url":"https://mayokoex.hatenablog.com/entry/2016/02/08/182047","provider_name":"Hatena Blog","blog_title":"mayoko\u2019s diary","type":"rich"}