题解
怎么看都不像是个背包，直到我看了题解→_→， 第一次碰到这么奇怪的背包= =
定一个滚动数组$F_i$， $i$表示机器$a$用了$i$的时间， $F_i$表示机器$b$用了$F_i$的时间， 然后就直接可以进行滚动转移了。。。
真是开眼界啊QuQ
代码
1 #include<cstring> 2 #include<algorithm> 3 #include<cstdio> 4 #define rd read() 5 #define rep(i,a,b) for(register int i = (a); i <= (b); ++i) 6 #define per(i,a,b) for(register int i = (a); i >= (b); --i) 7 using namespace std; 8 9 const int N = 8e3, inf = ~0U >> 3; 10 11 int n, m, f[N << 2]; 12 int a[N], b[N], ab[N]; 13 14 inline int read() { 15 int X = 0, p = 1; char c = getchar(); 16 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1; 17 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0'; 18 return X * p; 19 } 20 21 inline int cmax(int A, int B) { 22 return A > B ? A : B; 23 } 24 25 inline int cmin(int A, int B) { 26 return A > B ? B : A; 27 } 28 29 int main() 30 { 31 n = rd; 32 rep(i, 1, n) { 33 a[i] = rd; 34 b[i] = rd; 35 ab[i] = rd; 36 m += cmax(a[i], ab[i]); 37 } 38 f[0] = 0; 39 rep(i, 1, n) per(j, m, 0) { 40 int tmp = inf; 41 if(a[i] && j - a[i] >= 0) tmp = cmin(tmp, f[j - a[i]]); 42 if(ab[i] && j - ab[i] >= 0) tmp = cmin(tmp, f[j - ab[i]] + ab[i]); 43 if(b[i]) tmp = cmin(tmp, f[j] + b[i]); 44 f[j] = tmp; 45 } 46 int ans = inf; 47 rep(i ,0, m) ans = cmin(ans, cmax(i, f[i])); 48 printf("%d ", ans); 49 }