dynamic programming

Leetcode : 629. K Inverse Pairs Array

leetcode.com 問題概要 長さ n の順列を考える.反転数が k となる数列を数えなさい. 考察 一番愚直だと思われる解法は n! 通りの数列の反転数を計算し,kとなるものを数え上げるというものである. この計算量は O(nlogn*n!) であるがこれは明らかにTLEする…

ARC 078: F - Mole and Abandoned Mine

問題概要 arc078.contest.atcoder.jp 頂点数 ,辺の数 の無向グラフ が与えられるので,頂点 1 から頂点 へのパスが一通りになるように辺を取り除く. ただし,辺を取り除くにはコストがかかるため,取り除いた辺のコストの総和が最小となるようにする. 解…

Code Festival 2014 予選A

精神的にくるものがあったので久しぶりに記事を書く。 予選開始 A問題開く。通す。 B問題開く。通す。 C問題開く。通す。 D問題開く。貪欲に上から決めていけば解けそう…。 少し悩んでも良い実装が思い浮かばない。 しょうがなく桁DPを書く。 提出する。WA..…

JOI 2012-2013 本選 問題1 電飾

反転回数は最大でも1回かと思っていたけど2回だった。反省 #include <iostream> #include <vector> #include <algorithm> using namespace std; // 前回反転させた, 前回のランプ, 場所 int dp[3][2][100001]; int main() { int n, k, ans = 0; vector<bool> a; cin >> n; for(int i = 0; i < n;</bool></algorithm></vector></iostream>…

JOI 2013-2014 予選4番

最近forで回すDPの方が書きやすい、と感じている最初、鍵を持っている人の情報を持ってしまっていて重複したケースも数え上げてしまっていて時間が結構かかった。 #include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <algorithm> using namespace std; const </algorithm></map></vector></string></cstdio></iostream>…

PKU 1036

少し読解困難だった. はTLEするが,の処理は外に出すことができるためとなる. dp[i][j] := i時間で扉がjの状態であるときに,来訪するgang達の価値の総和の最大値#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <string> #include <map> using </map></string></vector></algorithm></cstring></cmath></cstdio></iostream>…

JMC 2014 4番

pastaっぽいと思った。作問のプロだと感じた(小並感) #include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <algorithm> using namespace std; int dp[128][128][2]; bool m[128][128]; const int MOD = 100000; int main() { int N, M, L, a, b; cin >> N >> M</algorithm></map></vector></string></cstdio></iostream>…

PKU 1014

JOI予選が近づいてきて,JOI予選の過去問解いてない後輩を煽るためPKUのDP問題解いてます(意味不明) 問題概要 価値が1から6まであるビー玉がある.入力には各々の価値のビー玉の個数が与えられている.二人はビー玉を任意の個数選び,ビー玉の価値を二等分…

AOJ 0263 Beat Panel

解法 パネルの状態を持ってメモ化再帰。 dp[i][S] := 今譜面iを見てパネルの状態Sのときの最大の獲得得点 勝手に前回使った運指は使わない(SRM?か何かでそんな感じの問題があったような…)という条件を付け足したことで冷え。 パネルの状態はbitとかvectorと…

AOJ 0561 Books

反省 dp[i][j][l] := 今までにi冊売り、今見ているジャンルjの本をl個売った時の最大の買取価格 最初はこれでDPしようとしたが、メモリが確実に収まらないのは自明だし(それでも頑張って削減して通そうとしたが)、書いている途中でlがいらないのにも気づいて…

AOJ 0568 Pasta

前の状態2つ考えないといけないと思ってたけど,1つで十分だった. やっぱメモ化再帰のほうが何も考えずに書ける. dp[i][j][k] := i日目にjのパスタをk個連続で作ったとき,i日目までの条件を満たす予定の数 n日目までの条件を満たす予定の数 ∋ i日目までの条…

ADLSI : 連鎖行列積

参考:アルゴリズムイントロダクション15章 動的計画法 コード中のコメントはここに書いてあることです…。 勘違いしてるかもしれません… ソースコード /* 連鎖行列積問題 演算結果はカッコ付けの順序にはよらないが、カッコ付けの順番には依存する ー>乗算回…

AOJ 0191 Baby Tree

方針 メモ化再帰. memo[i][j] := j番目の肥料を直前に与え,i回目の肥料を与える時の成長度の最大値 ソースコード double g[128][128]; double memo[128][128]; int n, m; double dfs(int c, int prev) { if(c == m) return 1.0; if(memo[c][prev] != -1) re…

AOJ 0154 Sum of Cards

方針 メモ化再帰. 主に下準備で面倒くさいコードになってしまいました. コード int memo[8][1024]; struct card { int value; // 値 int resid; // 残数 card(int a, int b) : value(a), resid(b) {} }; void input(int m, vector<card>& cards) { int a, b; for(i</card>…

AOJ 0089 The Shortest Path on A Rhombic Path

方針 再帰をしろという天からの声が聞こえた気がしたので,再帰を書いたのですがなぜか通らず. ということでfor文に直して解きました. dp[i][j] := i段目j個目まで選んだときの最大の値 半分より上の時と下の時で進む方向が変わるので注意です. コード int…