题解

1 条题解

  • 0
    @ 2020-09-12 20:59:15

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N = 20 + 5;
    int n, m, cnt, ans, tot, a[N][1005], sum[(1 << 20) + 5], len[N], s[N], f[(1 << 20) + 5];
    bool vis[25];
    int query(int now, int x){
    int l = 1, r = s[x], res = 0;
    while(l <= r){
    int mid = (l + r) >> 1;
    if(a[x][mid] <= now){
    res = mid;
    l = mid + 1;
    }else r = mid - 1;
    }

    return res;
    }
    signed main(){
    //freopen("t2.in","r",stdin); freopen("t2.out","w",stdout);
    scanf("%lld %lld", &n, &m);
    for(int i = 1; i <= n; i ++){
    scanf("%lld %lld", &len[i], &s[i]);
    for(int j = 1, x; j <= s[i]; j ++){
    scanf("%lld", &a[i][j]);
    }
    }
    ans = 1e9 + 5;
    for(int i = 1; i <= (1 << n) - 1; i ++){
    for(int j = 1; j <= n; j ++){
    if(i & (1 << (j - 1))){
    int t = query(f[i ^ (1 << (j - 1))], j);
    if(t) f[i] = max(f[i], a[j][t] + len[j]);
    }
    }
    }
    for(int i = 1; i <= (1 << n) - 1; i++) {
    sum[i] = sum[i ^ (i & (-i))] + 1;
    if(f[i] >= m) ans = min(ans, sum[i]);

    }
    if(ans == 1e9 + 5) ans = -1;
    printf("%lld\n", ans);
    fclose(stdin); fclose(stdout);
    return 0;
    }
    /*
    4 100
    50 3 15 30 55
    40 2 0 65
    30 2 20 90
    20 1 0
    */

  • 1

信息

难度
8
分类
(无)
标签
递交数
16
已通过
5
通过率
31%
上传者