[shape pressure dp] B005_LQ_ Candy (acceleration: contribution of pretreatment to each package of candy)

The owner of the candy store sells a total of M flavors of candy. For the convenience of description, we number m flavors as 1 ∼ M

Xiao Ming hopes to taste all kinds of candy. Unfortunately, the boss does not sell candy alone, but K pieces are sold in a package.

Fortunately, the taste of K sweets is indicated on the candy package, so Xiao Ming can know the taste of sweets in each package before buying.

Given N packages of candy, please calculate how many packages Xiaoming will buy at least, and then he can taste all kinds of candy.

input
The first line contains three integers N, M, and K
Next N lines, each line K, the integers T1, T2,..., TK, represent the mouth of a packet of candy
output
An integer represents the answer. If Xiaoming cannot taste all the flavors, output − 1

sample input 
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
 sample output 
2

For 30% of the evaluation cases, 1 ≤ N ≤ 20
For all evaluation samples, 1 ≤ N ≤ 100, 1 ≤ m ≤ 20, 1 ≤ K ≤ 20, 1 ≤ Ti ≤ M

Method 1: dp
  • Define status:
    • f[i] minimum number of packages required when candy collection status is I
  • Think about initialization:
    • f[…]=-1; f[0]=0; f[init_st]=1 there is a scheme for each package of initial candy
  • Consider the state transition equation:
    • f[i|st] = min(f[i|st], f[i]+1)
  • Thinking output: f[tot]

Details: the taste of candy is 1~M, which means that the taste needs to be subtracted by 1 when obtaining the state contribution;

This is violence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m,k; cin>>n>>m>>k;
    vector<vector<int>> A(n);
    
    int tot=(1<<m)-1, f[tot+5]; memset(f, -1, sizeof f);
    f[0]=0;
    for (int i=0; i<n; i++) {
        int st=0;
        for (int j=0; j<k; j++) {
            int x; cin>>x;
            A[i].emplace_back(x), st|=(1<<x-1);
        }
        f[st]=1;
    }
    for (int i=0; i<=tot; i++)if (f[i]!=-1) 
    for (int j=0; j<n; j++)  {
        int st=0;
        for (int x : A[j]) st|=(1<<x-1);
        if (f[i|st]==-1 || f[i|st]>f[i]+1)
            f[i|st]=f[i]+1;
    }
    cout << f[tot];
    return 0;
}

Complexity analysis

  • Time: O(2m×n×k)O(2^m × n × k)O(2m×n×k),
  • Space: O(2m)O(2^m)O(2m),

Here, because the contribution of each package of candy is fixed, an array of candy states can be preprocessed to optimize the O(k) time

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m,k; cin>>n>>m>>k;
    vector<vector<int>> A(n);
    
    int tot=(1<<m)-1, f[tot+5], ST[n]; memset(f, -1, sizeof f);
    f[0]=0;
    for (int i=0; i<n; i++) {
        int st=0;
        for (int j=0; j<k; j++) {
            int x; cin>>x;
            A[i].emplace_back(x), st|=(1<<x-1);
        }
        f[st]=1, ST[i]=st;
    }
    for (int i=0; i<=tot; i++) if (f[i]!=-1) 
    for (int j=0; j<n; j++)  {
        int st=ST[j];
        if (f[i|st]==-1 || f[i|st]>f[i]+1)
            f[i|st]=f[i]+1;
    }
    cout << f[tot];
    return 0;
}

Posted by j4IzbInao on Fri, 20 May 2022 09:55:51 +0300