Codeforces 295C Greg and Friends
問題
n人が一隻のボートを使って河を渡りたい。
ボートにはwKgまでの人が乗れる。i番目の人の重さはa[i]で、全て50または100kgのどちらかである。
ボートは一人以上の人間が乗っていないと動かせない。
全員が向こう岸に最短回数のボートの移動で移るような移動の仕方は何通りあるか、求めよ。
制約条件
n≦50
方針
こっちの岸に50キロの人がi人、100キロの人がj人いて、ボートがこっち側 = 0, あっち側 = 1にあるときの、
最短手数をdp[i][j][k]とする。
求めたいのは、dp[0][0][1]に至る場合の数。
最短路はDAGになっているので、経路の数を足してくようなDPをすればいい。
ソースコード
const int mod = (int)1e9 + 7; int C[110][110]; int n, w, dp[51][51][2], way[51][51][2]; int main(){ rep(i, 110) rep(j, i+1) C[i][j] = j == 0 || i == j ? 1 : (C[i-1][j] + C[i-1][j-1]) % mod; int x = 0, y = 0; cin >> n >> w; rep(i, n){ int t; cin >> t; if(t == 50) x++; else y++; } memset(dp, -1, sizeof(dp)); dp[x][y][0] = 0; way[x][y][0] = 1; queue<pair<pi, int> > q; q.push(mp(mp(x, y), 0)); while(!q.empty()){ int a = q.front().first.first, b = q.front().first.second; int c = q.front().second; q.pop(); if(a == 0 && b == 0 && c == 1) continue; if(c == 0){ rep(i, a + 1) rep(j, b + 1) if(i + j && i * 50 + j * 100 <= w){ if(dp[a - i][b - j][1] >= 0 && dp[a - i][b - j][1] <= dp[a][b][0]) continue; if(dp[a - i][b - j][1] < 0) q.push(mp(mp(a - i, b - j), 1)); dp[a - i][b - j][1] = dp[a][b][0] + 1; (way[a - i][b - j][1] += (ll)way[a][b][0] * C[a][i] * C[b][j] % mod) %= mod; } } else{ rep(i, x - a + 1) rep(j, y - b + 1) if(i + j && i * 50 + j * 100 <= w){ if(dp[a + i][b + j][0] >= 0 && dp[a + i][b + j][0] <= dp[a][b][1]) continue; if(dp[a + i][b + j][0] < 0) q.push(mp(mp(a + i, b + j), 0)); dp[a + i][b + j][0] = dp[a][b][1] + 1; (way[a + i][b + j][0] += (ll)way[a][b][1] * C[x-a][i] * C[y-b][j] % mod) %= mod; } } } cout << dp[0][0][1] << endl; cout << way[0][0][1] << endl; return 0; }