[TIOJ 1554] C-Game

作法：

題目簡單來說就是要在 n*n 的表格內取 n 個數，使得他們的乘積最大，所以很明顯可以想到是位元DP，如果 i 的二進制的 1 有 x 個，那麼 dp[ i ] 就等於在前 x 排裡每排各選 1 個數，並且他們都不同列，所可以產生的乘積最大值。另外因為懶的寫(?)算一個數的二進制的1個個數，所以直接用現有的 __builtin_popcount( x ) 。

另外題目裡面也沒也說答案要 * 100 後再輸出=ㄦ=

code :

#include<bits/stdc++.h>
#define LL long long
#define DB double
using namespace std;
const int maxn=20+2 ;
 
DB dp[1<<maxn] ;
int a[maxn] ;
vector<int> v[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<(1<<n);i++)
        v[__builtin_popcount(i)].push_back(i) ;
    dp[0]=1LL ;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<n;j++) scanf("%d",&a[j]) ;
        for(auto j : v[i]) for(int k=0;k<n;k++)
            if(j&(1<<k)) dp[j]=max(dp[j],dp[j^(1<<k)]*a[k]/100.0) ;
    }
    DB ans=(dp[(1<<n)-1])*100.0 ;
    printf("%.2f\n",ans+1e-5) ;
}