DP

POJ 3411: Paid Roads

http://poj.org/problem?id=3411問題文をよく読みましょう。(a,b)は有向辺です。無向辺でやったあとを残しておきました。 ベルマンフォードっぽくbitDPをやればよい。 int N, M; int A[20], B[20], C[20], P[20], R[20]; int dp[1 << 11][11]; int main() { …

AtCoder Regular Contest 078F: Mole and Abandoned Mine

http://arc078.contest.atcoder.jp/tasks/arc078_d3^Nの形になるdpなんて初めて見た。まず使う辺に注目して、それらのコストの和を最大化する。 dp[S][v]:=(集合Sの点を使う際で0~v間でpathがただ一つ存在するための最大値)とする。遷移は二種類ある。 (1)pa…

POJいろいろ8/2

2441 http://poj.org/problem?id=2441bitdpやるだけしたら3938MS/4000MSで超ギリギリだったw3254 http://poj.org/problem?id=3254sampleも一発で通って気持ちがいい。bitdp。3420 http://poj.org/problem?id=3420行列累乗。一行ごとのstateをbitで表して行列…

Codeforces Round #419C: Karen and Supermarket

http://codeforces.com/contest/815/problem/C3乗っぽいけど2乗な木dp。 5000*5000*2のlong longの配列持ったらMLEした。 さらに初期化を適当にやりすぎてO(N^3)になってしまった。 直してAC。 int N, B; vector<int> G[MAX_N]; int dp[MAX_N][MAX_N][2]; int dp2</int>…

AtCoder Regular Contest 073F: Many Moves

http://arc073.contest.atcoder.jp/tasks/arc073_ddp高速化。dp[i][j]:=(i番目のqueryまで処理して、2点の座標がx[i]とjの時の最小値)とする。 するとdp[i][j]+jとdp[i][j]-jの値についてrange_sumとrange_minが出来れば高速に更新できる。2つsegtreeを持た…

AOJ 2415: Sashimi

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 monge(もんじゅ)dp。http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915 と http://sssslide.com/www.slideshare.net/ikumihide/ss-50881829 を参考にした。単調性が本質で、それを…

AtCoder Regular Contest 070D: No Need

DP

http://arc070.contest.atcoder.jp/tasks/arc070_bなんとなくの解法ならすぐわかったけど、それを詰めるのがつらかった。0~i-1の和をsum[i]と表す。aをsortしてai~aNの要素のうちいくつかを選んで和を作る。その内、Kを超えないもので最大の値をJとする。 す…

AOJ 2749: ぼくのかんがえたさいきょうのおふとん

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2749&lang=jp sortしてbit dp。 int N, M; int dp[(1 << 16) + 10][110]; int O[20]; int A[110]; void solve() { while(true) { cin >> N >> M; if(N == 0) break; rep(i, 0, N) cin >> O[i]; re…

AtCoder Regular Contest 074 E: RGB Sequence

DP

http://arc074.contest.atcoder.jp/tasks/arc074_cひたすらdp[i][j][k](i番目まで見たときRがj個あり、Gがk個ある場合の数)みたいな感じでやろうとしたけど、区間内にRGBがそれぞれ存在するかどうかだけわかればいいのでどう見ても情報を持ちすぎていた。 dp…