# 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