じりきで解けなかった。 漸化式作るのむずかしすぎ(頭悪い) #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 15; int N, M; int cup[MAX_N]; int main(){ while(scanf("%d %d",&N,&M)&&N!=0){ for(int i=0; i<3; i++){ int K; scanf("%d", &K);</algorithm></cstdio>…

問題 解法 動的計画法を使う。 三角形を高さiの二次元配列に入れたとき、漸化式は dp[i][j] = triabgle[i][j] + max(dp[i-1][j], dp[i-1][j-1]) #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 101; int tri[MAX_N][MAX_N]; int dp[MAX_N][MAX</algorithm></cstdio>…

問題 解法 動的計画法をつかえば解ける。 詳しくはソース中のコメントみてください。 O(F*V)だからはやい。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_F = 100, MAX_V = 100, MINF = -(1<<29); int F, V; int table[MAX_F + 1][MAX_V + 1]; i</algorithm></cstdio>…

問題 解法 動的計画法が使える。 詳しくはソースで #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_STRLEN = 4001; int len1, len2; char str1[MAX_STRLEN]; char str2[MAX_STRLEN]; int dp[MAX_STRLEN][MAX_STRLEN]; int solve(){ int </algorithm></cstring></cstdio>…

久しぶりのDP。DPの考え方を一瞬わすれた。日頃からやっとかないとだめですね。 問題 これ #include <cstdio> using namespace std; int t[]={ 0,0,380,550,760,850,1100,1230,1400,1610,1520,1950,1870, 2070,2250,2244,2620,2624,2794,3004,3040,3344,3390,3590, 3</cstdio>…

アルゴリズムデザインにのっていたので、c++で実装してみた。 系列アライメントとは、Googleの「もしかして:」の機能のような似ている文字列を探すやつのこと。 二つの文字列で動的計画法を使って類似度を計算する。入力単語(辞書) ... # チェックする単語 .…

「アルゴリズムデザイン」にのっている演習問題。 ストーリーが、某主人公が救世主になってマシンと戦争する映画にとてもにている。がその辺は省略。 問題 n秒間に渡りロボットがくる。i秒目にはXi台のロボットがくることが分かっている。 ロボットを倒すた…

3をかけていくだけの簡単なお仕事です。 #include <cstdio> using namespace std; const int MAX_N = 20; long long table[MAX_N + 1]; int main(){ int n; table[1] = 3; for(int i = 2; i <= MAX_N; i++) table[i] = table[i-1]*3; scanf("%d", &n); for(int i = 1</cstdio>…

ナップサック問題とくだけ。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 1000; const int MAX_W = 1000; int W, N; int w[MAX_N + 1], v[MAX_N + 1]; int dp[MAX_N + 1][MAX_W + 1]; /* dp[i][j] := i番目までの品物を重さj以下となるよう</algorithm></cstdio>…

動的計画法で解ける。 dp[i][j] = map[i][j] + min(dp[i - 1][j], dp[i][j - 1]) 上の漸化式を順番に当てはめていけば、その地点までの最小のセミの数になっている。 そして、dp[H][W]がこたえになる。 #include <cstdio> #include <queue> #include <algorithm> using namespace std; </algorithm></queue></cstdio>…

bitDPで解けた。 ビットの例…11001001 1,4,7,8のアイテム #include <cstdio> #include <algorithm> using namespace std; const int INF = 10000000; const int MAX_N = 16; const int MAX_C = 1 << MAX_N; int table[MAX_N + 1][MAX_N + 1];//ステージnをアイテムmでクリアする</algorithm></cstdio>…

解くコードを書いてみた。 漸化式を思いつけるようになりたい。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100; //品物の最大個数 const int MAX_W = 10000; //最大の重さ int N, W; //品物の個数、ナップサックに入る重さ typedef pair<int ,int> </int></algorithm></cstdio>…

動的計画法をマスターすべく、アリ本で修行している。 DPの意味が何となく分かってきた。 漸化式を作るのが非常にむずかしい。