1 条题解
-
0Tethys LV 9 @ 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%
- 上传者