動的計画法

SRM602 div1 Easy TypoCoderDiv1

メモ 動的計画法。 dp[i+1][j] := i個目まででレートがjの時の色が変わった回数の最大値とする。レートjにならない時は-1とする。 レートは109以上になるため工夫しないとTLE。 2200以上が2回以上続くことが禁止されているため、2200未満のレートだけ考えれ…

ARC067 E - Grouping

解説 dp[i][j] = i人未満のグループのみで、j人を分ける通り数とする。 このようにdpを定義すると、dpの更新式は以下のようになる。 i人のグループを一個も作らないとき、 残りのN-j人のうち、i人のグループをk個作るとき、 で割るのはグループを区別しない…

AOJ 2199 - Differential Pulse Code Modulation

Differential Pulse Code Modulation | Aizu Online Judge 解説 dp[i][j] := i個目の信号まででyがjのときの最小値 コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include </vector></string></stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>

【AtCoder】ABC040 C. 柱柱柱柱柱

AtCoderの問題 C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ(初心者目線) ・考え方** ・実装*** ・面白さ** 問題概要 ・柱が1列にN本並んでいる. ・それぞれの柱の高さはであ…

【GCJ】2009_1C Problem C. Bribe the Prisoners

AtCoderの問題 Dashboard - Round 1C 2009 - Google Code Jam 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ(初心者目線) ・考え方***** ・実装*** ・面白さ**** 問題概要 ・P人の囚人が一列の牢屋にいる(独房) ・あなたはQ人を解放し…

【AtCoder】ABC044 C. 高橋君とカード

AtCoderの問題 C: 高橋君とカード / Tak and Cards - AtCoder Beginner Contest 044 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 現在AtCoderの過去問AB(たまにC)解いてます. 難しさ(初心者目線) ・考え方*** ・実装** ・面白さ**…

【yukicoder】No.4 おもりと天秤

yukicoderさんの問題 No.4 おもりと天秤 - yukicoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ(初心者目線) ・考え方*** ・実装*** ・面白さ** ヒント(カーソル合わせると見れます) コード #include <algorithm> #include <cstdio> #include <iostream> #includ</iostream></cstdio></algorithm>…

【yukicoder】No.45 回転寿司

yukicoderさんの問題 No.45 回転寿司 - yukicoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ(初心者目線) ・考え方*** ・実装*** ・面白さ*** ヒント(カーソル合わせると見れます) コード #include <algorithm> #include <cstdio> #include <iostream> #include <map></map></iostream></cstdio></algorithm>…