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