[백준]3056 007

jyukki included in 백준

2020-04-18 228 words 2 minutes

Contents

https://www.acmicpc.net/problem/3056

풀이:

d[x] : 비트마스크가 x인 미션을 완료 할 확률

비트마스크 x : 나누어 준 미션은 1, 아직 나누어 주지 않은 미션은 0

비트마스크가 1, 10, 100, 1000 ….. 등 1의 갯수가 1개인 것은 첫 번째 지미 본드가 수행한다고 한다.

비트마스크가 11, 110, 1100, 11000 ….. 등 1의 갯수가 2개인 것은 두 번째 지미 본드가 수행한다고 한다.

….

비트마스크를 0 ~ (1 « n) 까지 순회한다.

현재의 비트마스크를 i 라고 하자, 그 비트의 중간에 0이 들어있다면, 그 위치에 1을 넣는다.

즉, d(i | (1 « t)(t번째 위치에 0값을 1로 바꿈)) = max(d[i | (1 « t),

d[i] * a[(비트마스크의 1의 갯수)(1의 갯수가 지미 본드의 번호)][t(몇 번째 미션을 수행하는지)] / 100)

로 구할 수 있다.

출력할 때 %.6f 로 출력하는 것 잊지말자!!!!!!!!!!!!!!!!

코드:

사용언어 : c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


#include <iostream>
#include <algorithm>
using namespace std;
int n, i, t, a[23][23];
double d[(1 << 22)] = { 1 };
int main() {
	cin >> n;
	for (; i < n; i++)for (t = 0; t < n; t++)cin >> a[i][t];
	for (i = 0; i < (1 << n);i++)
		for (t = 0; t < n; t++)
			if (!(i & (1 << t)))
				d[i | (1 << t)] = max(d[i | (1 << t)], 
                                      d[i] * a[__builtin_popcount(i)][t] / 100);
	printf("%.6f", 100 * d[(1 << n) - 1]);
}