問題要約：Aはa個の1からbまでの整数が同様に確からしい確率で出るサイコロを持っている。Bはc個の1からdまでの整数が同様に確からしい確率で出るサイコロを持っている。今A,Bがすべてのサイコロをふって自分のサイコロの総和Sa,Sbを求めたところSa>Sbであっ…

昨日の夜、解いた。漸化式むずかしい #include <cstdio> #include <algorithm> using namespace std; const int INF = 1<<29; const int MAX_N = 10000; int N; int a[MAX_N]; int dp[2][MAX_N][2]; int main(){ scanf("%d", &N); a[0] = 0; for(int i = 1; i < N; i++) scanf("</algorithm></cstdio>…

問題解法 10^7回も散歩する太郎君の問題 解説みた。動的計画法を使う。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_HW = 1000; int N, H, W; int a[MAX_HW + 2][MAX_HW + 2]; int dp[MAX_HW + 2][MAX_HW + 2]; int main(){ while(scanf("%d %d</algorithm></cstdio>…

今日はJOI予選です。5完を目指します 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530解法 動的計画法をつかう 横の列の個数分の配列をとるとTLEしそう。 そこで、一つの行には石がたかだか10個しかないという制約を利用するとはやくな…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557解法 動的計画法 状態は [i][j] = i番目の数字までを使ってjを作る+-の入れ方の総数 とした。 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int a[101]; ll dp[101]</algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547解法 動的計画法。 #include <cstdio> #include <algorithm> using namespace std; const int MOD = 100000; typedef pair<int, int> P; typedef pair<P, P> PP; PP dp[101][101]; int main(){ int h, w; for(int i=0; i < 1</p,></int,></algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0538解法 動的計画法を使う。 Oの数を数えることを意識して、 a[i] = if(s[i-1]=='I' && s[i]=='O' && s[i+1] == 'I') a[i-2] + 1 else 0 という漸化式を作り、aの中に何個N以上の数があるか…

スタンプの長さのとりうる値の範囲は 0[i-l+1, i]をスタンプで色j(それより前は何の色でもよい)で塗る, という条件で 塗る方法の数 というDPを思いついた。 あとは漸化式たてて解いて、最小となるLを見つけて計算する。 O(N^4)ぐらいだと思う #include <cstdio> #inc</cstdio>…

問題 http://poj.org/problem?id=2704解法 ゴールから逆にたどるように考えるといい。ゴールの方から道をみると下のような漸化式が成り立つ。a[i][j] := そのマスに書いてある数字 dp[i][j] := そこの場所からゴールまで行き方の総数dp[N-1][N-1] = 1 dp[i][…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011解法 T日にスケジュールのあいている子孫の集合をCtとする 子孫cがT日に持っている地図の集合をMctとするMct = Mc(t-1) (c ∈ Ct でない) ∪{Md(t-1) | d ∈ Ct} (c ∈ Ct) を計算していって…

http://poj.org/problem?id=1948自力で解けなかった。 なんか、頭いい方法でDPするらしい。 こんなループのまわし方はどうやったら思いつくのだろうか。 #include <cstdio> #include <math.h> #include <algorithm> using namespace std; const int M_N = 40; const int M_L = 40; int N</algorithm></math.h></cstdio>…

JOI予選のとき、動的計画法ということには気づいたけど頭悪いのでどうすればよいか分からなかった問題。 教訓：とりあえず再帰関数 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568 解法 動的計画法またはメモ化再帰をつかう。 メモ化…

問題 解法 動的計画法をつかうA(t,p) := (時間tに木pからりんごが落ちてくる) ? 1 : 0 dp[t][p][w] := 時間tで,木pの下にいて,移動回数w以下のときの最大のりんごの数と定義すると、漸化式はdp[t][p][w] := max(dp[t][p][w+1], max(dp[t-1][p][w] + A(t,p), …

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202以前問題を見たとき「あ、これ無理なやつだ」と思ったもの。 できるようになっていた。解法 素数の金額が作れるかを調べるのに動的計画法を用いる。 ↑この発想がむりだった。 k[i] := 品物iの…

問題 解法 ダイクストラ法を使って、ああでもないこうでもないとやっている うちになぜか解けてしまったのでよくわからない。 動的計画法も使っているような気がする…だけかもしれない。 割引券の枚数に対する最短距離？みたいなのを計算していく？というよ…