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;
}