挺无语的状态压缩题目,太显然了.
\(f[i]\)表示状态为i的最远到达的距离.
然后暴力枚举每一个可行的点.
然后二分一下即可..
/*header*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <cmath>#define rep(i , x, p) for(int i = x;i <= p;++ i)#define sep(i , x, p) for(int i = x;i >= p;-- i)#define gc getchar()#define pc putchar#define ll long long#define mk make_pair#define fi first#define se secondusing std::min;using std::max;using std::swap;const int maxN = 20 + 3; inline int gi() { int x = 0,f = 1;char c = gc; while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;} while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}return x * f;} void print(int x) { if(x < 0) pc('-') , x = -x; if(x >= 10) print(x / 10); pc(x % 10 + '0');}int f[1048600] , time[maxN], beg[maxN][1007] , num[1048600];int search(int p , int x) { int l = 1 , r = time[p] , mid , ans = -1; while(l <= r) { mid = (l + r) >> 1; if(beg[p][mid] <= x) ans = mid , l = mid + 1; else r = mid - 1; } return ans;}int main() { int n = gi() , L = gi(); rep(i , 1, n) { time[i] = gi(); int m = gi(); rep(j , 1, m) beg[i][j] = gi(); } memset(f , 0x3f, sizeof(f)); f[0] = 0; rep(i , 1, (1 << n) - 1) { rep(j , 1, n) { if(i & (1 << j - 1)) { int p = search(j , f[i ^ (1 << (j - 1))]); if(p != -1) f[i] = max(f[i] , beg[j][p] + time[j]); } } } int ans = 1e9; rep(i , 1, (1 << n) - 1) { num[i] = num[i - (i & (-i))] + 1; if(f[i] >= m) ans = min(ans , num[i]); } printf("%d\n", ans == 1e9 ? -1 : ans); return 0;}
