YEZAELP

PROG-1036: Equipped

Jun 28th, 2020 (edited)
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. const int maxN = 1e4;
  6. const int maxK = 8;
  7. int cost[maxN + 10], bit[maxN + 10];
  8. int dp[maxN + 10][(1 << maxK) + 10];
  9. int N, K, Bit;
  10.  
  11. int f(int i, int b){
  12.     if((b & Bit) == Bit) return 0;
  13.     if(i == N) return inf;
  14.     if(dp[i][b] != inf) return dp[i][b];
  15.     int x = cost[i + 1] + f(i + 1, (b | bit[i + 1]));
  16.     int y = f(i + 1, b);
  17.     return dp[i][b] = min(x, y);
  18. }
  19.  
  20. int main(){
  21.  
  22.     scanf("%d %d", &N, &K);
  23.  
  24.     Bit = (1 << K) - 1;
  25.  
  26.     for(int i=1;i<=N;i++){
  27.         scanf("%d", &cost[i]);
  28.         for(int k=K-1;k>=0;k--){
  29.             int b; scanf("%d", &b);
  30.             bit[i] = bit[i] | (b << k);
  31.         }
  32.     }
  33.  
  34.     for(int b=Bit-1;b>=0;b--)
  35.         dp[N][b] = inf;
  36.     dp[N][Bit] = 0;
  37.  
  38.     for(int i=N-1;i>=0;i--){
  39.         for(int b=Bit;b>=0;b--){
  40.             dp[i][b] = min( cost[i + 1] + dp[i + 1][b | bit[i + 1]] , dp[i + 1][b] );
  41.         }
  42.     }
  43.  
  44.     printf("%d", dp[0][0]);
  45.  
  46.     return 0;
  47. }
RAW Paste Data Copied