Advertisement
YEZAELP

PROG-1038: Bond

Jun 29th, 2020
140
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using pii = pair<int,int>;
  5. const double INF = 1e9;
  6.  
  7. int n,Bit;
  8. double ar[30][30];
  9. vector <double> dp(1048575,-INF);
  10.  
  11. double bond(int bit,int i){
  12.     if(bit == Bit) return 1.0;
  13.     if(dp[bit] != -INF) return dp[bit];
  14.     for(int j=0; j<n; j++){
  15.         if(bit & (1<<j)) continue;
  16.         dp[bit] = max(dp[bit], ar[i][j] * bond(bit | 1<<j,i+1) );
  17.     }
  18.     return dp[bit];
  19. }
  20.  
  21. int main(){
  22.  
  23.     scanf("%d",&n);
  24.  
  25.     for(int i=0; i<n; i++){
  26.         for(int j=0; j<n; j++){
  27.             int x;
  28.             scanf("%d",&x);
  29.             ar[i][j] = (double)x/100.0;
  30.         }
  31.     }
  32.  
  33.     Bit = (1<<n) - 1;
  34.     printf("%.6f",bond(0,0)*100);
  35.  
  36.     return 0;
  37. }
Advertisement
RAW Paste Data Copied
Advertisement