Advertisement
Saleh127

UVA 10702 / Bitmask DP

Jan 28th, 2022
935
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-27-23.47.37
  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. int f[500];
  13. int a[105][105];
  14. int dp[105][1005];
  15. int n,s,c,e,t;
  16.  
  17. int solve(int in,int city)
  18. {
  19.      if(dp[in][city]!=-1) return dp[in][city];
  20.      if(city==0)
  21.      {
  22.           if(f[in]) return 0;
  23.           else return INT_MIN;
  24.      }
  25.  
  26.      int ans=INT_MIN;
  27.  
  28.      for(int i=1;i<=c;i++)
  29.      {
  30.           if(in!=i)
  31.           {
  32.                ans=max(ans,a[in][i]+solve(i,city-1));
  33.           }
  34.      }
  35.  
  36.      return dp[in][city]=ans;
  37. }
  38.  
  39. int main()
  40. {
  41.    ios_base::sync_with_stdio(0);
  42.    cin.tie(0);cout.tie(0);
  43.  
  44.  
  45.    while(cin>>c>>s>>e>>t && (c+s+e+t)!=0)
  46.    {
  47.         for(int i=1;i<=c;i++)
  48.         {
  49.              f[i]=0;
  50.              for(int j=1;j<=c;j++)
  51.              {
  52.                   cin>>a[i][j];
  53.              }
  54.         }
  55.  
  56.         for(int i=1;i<=e;i++)
  57.         {
  58.              int m;
  59.              cin>>m;
  60.              f[m]=1;
  61.         }
  62.  
  63.         memset(dp,-1,sizeof dp);
  64.  
  65.         cout<<solve(s,t)<<nl;
  66.    }
  67.  
  68.    get_lost_idiot;
  69. }
  70.  
  71.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement