Advertisement
Saleh127

Light OJ 1018 / Bitmask DP

Jan 28th, 2022
1,391
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-28-23.13.14
  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 dp[(1<<16)+2],clinear[20][20];
  17.  
  18. ll x[20],y[20],n;
  19.  
  20. ll solve(ll mask)
  21. {
  22.      if(dp[mask]!=-1) return dp[mask];
  23.  
  24.      if(mask==(1<<n)-1) return 0;
  25.  
  26.      if(mask==(1<<(n-1))-1 || mask==(1<<(n-2))-1) return 1;
  27.  
  28.      ll ans=1e5;
  29.  
  30.      for(ll i=0;i<n;i++)
  31.      {
  32.           if(check(mask,i)==0)
  33.           {
  34.                for(ll j=i+1;j<n;j++)
  35.                {
  36.                     if(check(mask,j)==0)
  37.                     {
  38.                          ans=min(ans,1+solve(mask|clinear[i][j]));
  39.                     }
  40.                }
  41.                break;
  42.           }
  43.      }
  44.  
  45.      return dp[mask]=ans;
  46. }
  47.  
  48. bool colinear(ll i,ll j,ll k)
  49. {
  50.      if((x[i]*y[j])+(x[j]*y[k])+(x[k]*y[i])==(x[i]*y[k])+(x[k]*y[j])+(x[j]*y[i])) return 1;
  51.      return 0;
  52. }
  53.  
  54. int main()
  55. {
  56.    ios_base::sync_with_stdio(0);
  57.    cin.tie(0);cout.tie(0);
  58.  
  59.    test
  60.    {
  61.         cin>>n;
  62.  
  63.         for(ll i=0;i<n;i++)
  64.         {
  65.              cin>>x[i]>>y[i];
  66.         }
  67.  
  68.         memset(dp,-1,sizeof dp);
  69.         memset(clinear,0,sizeof clinear);
  70.  
  71.         for(ll i=0;i<n;i++)
  72.         {
  73.              for(ll j=i+1;j<n;j++)
  74.              {
  75.                   for(ll k=0;k<n;k++)
  76.                   {
  77.                        if(colinear(i,j,k)==1)
  78.                        {
  79.                             clinear[i][j]|=(1ll<<k);
  80.                        }
  81.                   }
  82.              }
  83.         }
  84.         cout<<"Case "<<cs<<": "<<solve(0)<<nl;
  85.    }
  86.  
  87.  
  88.  
  89.    get_lost_idiot;
  90. }
  91.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement