Advertisement
Saleh127

Light OJ 1011 / Bitmask DP

Jan 23rd, 2022
901
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-23-16.31.44
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll Set(ll N,ll pos){return N=N |(1<<pos);}
  13. ll reset(ll N,ll pos){return N= N & ~(1<<pos);}
  14. bool check(ll N,ll pos){return (bool)(N & (1<<pos));}
  15.  
  16. ll n,dp[17][1ll<<16];
  17. ll a[17][17];
  18.  
  19. ll solve(ll in,ll mask)
  20. {
  21.      if(mask==(1<<n)-1) return 0;
  22.  
  23.      if(dp[in][mask]!=-1) return dp[in][mask];
  24.  
  25.      ll ans=0;
  26.  
  27.      for(ll i=0;i<n;i++)
  28.      {
  29.           if(check(mask,i)==0)
  30.           {
  31.                ans=max(ans,a[in][i]+solve(in+1,Set(mask,i)));
  32.           }
  33.      }
  34.  
  35.      return dp[in][mask]=ans;
  36. }
  37.  
  38. int main()
  39. {
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0);
  42.     cout.tie(0);
  43.  
  44.     test
  45.     {
  46.          cin>>n;
  47.  
  48.          for(int i=0;i<n;i++)
  49.          {
  50.               for(int j=0;j<n;j++)
  51.               {
  52.                    cin>>a[i][j];
  53.               }
  54.          }
  55.  
  56.          cout<<"Case "<<cs<<": ";
  57.  
  58.          memset(dp,-1,sizeof dp);
  59.  
  60.          cout<<solve(0,0)<<nl;
  61.     }
  62.  
  63.     get_lost_idiot;
  64. }
  65.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement