ナップサック問題とくだけ。 #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>…

硬貨の枚数を少なくしたい。 所持金をすべて払ったときのおつりを求め、そこから重複して払った硬貨の枚数を 引いていけばいい。たぶん一瞬で解が求まるから、８秒の時間制限も余裕。 #include <cstdio> #include <algorithm> using namespace std; int p; //代金 int coin[4]; </algorithm></cstdio>…

最初、一日はたかだか864000秒しかないことを利用して解こうとしたが なぜかWrongAnswerだらけになるので、あきらめた。 結局、自力では解けなかった。 列車が行くとインクリメント、着くとデクリメントというやりかたでいけるらしいので やってみたらAC。 …

JOI予選の結果が発表されていた。 問題1,2 各20点 問題3 8点 他0点 合計48点 Bランク反省 問題1,2はすぐ解けて、他は手も足も出ないという状況だった。 問題3は今考えると、全部試す必要がなくて、単純な方法で いけることが分かってすごく悔しい。こういう…

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 <queue> #include <algorithm> using namespace std; typedef pair<int, int> P; typedef pair<int, P> D; //ターン数、位置</int,></int,></algorithm></queue></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の意味が何となく分かってきた。 漸化式を作るのが非常にむずかしい。

JOI 予選でハニカム構造が出てきて、手も足も出なかったのでつくってみた。 最初の2つは普通の正方形が並べられている形。 次がハニカム構造。4つめが三角形が敷き詰められた形。 上記のようなときにこれを使って探索とかすると、たぶん便利。 /* 四角形のと…

左上から右下にかけて順番にたどっていき、何個のループがあるか数える。 一度通った場所には印をつけ、ループになっているか確かめながらたどっていくとよい。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100; int N; typedef pair<int, int> P; P </int,></algorithm></cstdio>…

HelloWorld.cpp #include <cstdio> using namespace std; int main(){ printf("HelloWorld!\n"); return 0; }</cstdio>

競技プログラミングのこととかについて書いていく予定。