[3056] 007

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

3056번: 007

<문제>

메모이제이션+브루트포스+비트마스킹으로 해결할 수 있다.

입력받을때 /100을 해두고, 출력할때 *100을 해주었다.

하나의 depth당 행렬에서 하나의 행을 선택하도록 만들어 주었고, 어떤 열을 선택했는지를 비트마스킹으로 표현한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n;
double ans, a[22][22];
double dp[1 << 20];
double f(int bt, int depth) {
    if (depth == n) return 1;
    if (dp[bt] != -1) return dp[bt];
    int i;
    for (i = 0; i < n; i++) {
        if (bt & (1 << i)) continue;
        int nbt = bt | (1 << i);
        dp[bt] = max(a[depth][i] * f(nbt, depth + 1), dp[bt]);
    }
    return dp[bt];
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            cin >> a[i][j];
            a[i][j] /= 100;
        }
    fill(&dp[0], &dp[1 << 20], -1);
    cout << fixed << setprecision(6);
    cout << (double)100 * f(0, 0);
    return 0;
}