BOJ 3056 : 007

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

모든 경우의 수를 찾는데 백트래킹으로 하면 시간 많이 걸리니 Bit DP를 돌리자(?).

계산 조심하면 AC.

#include <bits/stdc++.h>
#define MEM 20
#define sanic ios_base::sync_with_stdio(0)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e9+7;
ll n,ans;
double mp[MEM][MEM];
double dp[1<<MEM];
double deepee(int c, int b){
    if(c==n) return 1;
    double &ret=dp[b];
    if(ret!=0.0) return ret;
    for(int i=0; i<n; i++){
        if(!(b&(1<<i)))
            ret = max(ret, deepee(c+1, b|(1<<i))*(mp[c][i]));
    }
    return ret;
}
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            cin >> mp[i][j];
            mp[i][j]/=100.0;
        }
    cout.precision(6);
    cout << fixed << deepee(0,0)*100.0;
}