問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089 動的計画法で解いた。 dp[ i行目 ][ j列目 ]:=最大コストとすると、i行目のj列目にはi-1行目の同じj列と i i>N のとき i-1行目のj+1列目 (Nは行数) から来れるので、この2ヶ所までの…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530 DAGの最短経路はDPで簡単に求めることができる。 dp[i行目][左からj番目][1行飛ばしの残り回数]:=最小コスト #include<iostream> #include<vector> #include<queue> #include<cmath> #include<algorithm> #define f first #define</algorithm></cmath></queue></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568 動的計画法で解いた。dp[i日目][j種類目のパスタ][l日連続]:=組み合わせの数 #include<iostream> #include<algorithm> #include<vector> #define A first #define B second using namespace std; typedef pair<int,int> P; i</int,int></vector></algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 動的計画法で解いた。dp[マスの番号][所持金]:=マス i に所持金 j で行ける確率とすると、 人生ゲームにイベントマスがなければ dp[i + v[k] ][j] += dp[i][j]/xv[k]はルーレットの数…

問題文POJ http://poj.org/problem?id=1088UVa http://uva.onlinejudge.org/external/102/10285.html縦r,横cのグリッドが与えられる。 上下左右で、数字が現在のセルより小さいセルにのみ移動可能。 移動できる最長経路の長さを求めよ。 メモ化再帰した。 PO…

問題文 http://poj.org/problem?id=1014 1から6までの価値がついたビー玉を二人で分けたい。 ビー玉の個数が与えられるので同じ価値になるように わけられるかどうか判定せよ。 動的計画法で解いた。 ビー玉の価値の合計の半分が作れればよい。 個数制限つき…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2431 (全ての荷物の重さ)-(最長増加部分列の重さ)が答えになる。dp[ i ]:= i 番目を最後尾とする最長増加部分列の重さ dp[ i ]=max(dp[ j ] | 0 i未満の番号の最長増加部分列の最大値を求…

蟻本を参考にした。 ビットDPで解いた。 dp[使った乗車券の集合][都市の番号]:=最小コスト #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #define INF (1<<29) using namespace std; int main(void){ int n,m,p,a,b,x,y,z,in; double dp[(1<<8)][31],graph[31][31]; </cstdio></algorithm></vector></iostream>…

バルーンが落ちてくる位置と時間が与えられる。 台車が運べるバルーンは３つまでである。 全てのバルーンを拾うことができるか。 また、そのときの最小の移動距離は？ もし全てのバルーンを拾うことができなければ 拾うことができない最初のバルーンの番号を…

0 から 100 の数字から異なる n 個の数を取り出して 合計が s となる組み合わせの数を求める問題。 動的計画法で解いた。 dp[取り出す個数][合計]:=組み合わせの数 #include <iostream> using namespace std; long long n,s,dp[11][1001]; int main(void){ dp[0][0] = </iostream>…

ビットDPで解いた。 dp[ビート音の数][ボタンの押し方]:=得点の最大値立っているビットの数を数える関数countは http://tak5219.seesaa.net/article/7042181.html を参考にした。 #include<iostream> #include<algorithm> #include<cstring> using namespace std; int a[30],b[30],dp[31][1<</cstring></algorithm></iostream>…

DAGが与えられるので、最長経路を求める問題。 ただしノードPで作業を開始するためには Pまでの最長日数が経っている必要がある。トポロジカルソートしてからDPした。 dp[i]:=結合点iまでの最長日数 #include<iostream> #include<algorithm> #include<vector> #define INF 100000000 using</vector></algorithm></iostream>…

動的計画法で解いた。 dp[i]:=長さiのメロディの得点の最大値 #include<iostream> #include<algorithm> using namespace std; int main(void){ int n,m,s[400],l[400],p[400],w[400],dp[400]; cin >> n; for(int i=0;i<n;i++) cin >> s[i] >> l[i] >> p[i]; cin >> m; for(int i=0;i<m;i++)cin >> w[i]; fil</m;i++)cin></n;i++)></algorithm></iostream>…

動的計画法で解いた。dp[ i ][ j ] := i+2日目に服Xjを選んだ場合の派手さの差の合計の最大値 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void){ int d,n,t,a,b,c,dp[202][202]; vector<int>T,A,B,C; cin >> d >> n; for(int i=0;i<d;i++){ cin >> t; T.push_ba</d;i++){></int></algorithm></vector></iostream>…

動的計画法で解いた。dp[ i ][ j ]:=i番目までのカードでj円を作れるパターンの数 #include<iostream> using namespace std; int main(void){ int m,a[8],b[8],g,n,dp[8][1001]; while(cin >> m,m){ for(int i=0;i<8;i++){ for(int j=0;j<1001;j++){ dp[i][j]=0; } } f</iostream>…

つららの長さがすべて0になるまでの時間を求める。 lをつららの長さの上限として、dp[i]:=i番目のつららの長さa[i]がlになるまでの時間if(a[i]>a[i-1] && a[i]>a[i+1])dp[i] = l-a[i] else dp[i] = max(dp[i-1], dp[i+1]) + l-a[i] #include<iostream> #include<vector> #inclu</vector></iostream>…

メモ化再帰で解いた。 dp[i][j][p]:=現在(i,j)にいて、状態pである。i…南北 j…東西p= 1…直前に曲っていて、東に進んでいる →東に進み、p=32…直前に曲っていて、北に進んでいる →北に進み、p=43…直前に曲っていない、東に進んでいる →東に進み、p=3 または 北…