- #include < stdio.h > #include < string.h > #include < stdlib.h > #include < algorithm >
- //#include<iostream>
- using namespace std;
- int n,
- m,
- t;#define maxn 111#define maxm 25011 int f[maxm],
- g[maxm],
- v[maxn],
- c[maxn];
- int que[maxm],
- head,
- tail,
- id[maxm],
- vmax;
- const int inf = 0x3f3f3f3f;
- int main() {
- scanf("%d%d", &n, &t);
- vmax = 0;
- for (int i = 1; i <= n; i++) scanf("%d", &v[i]),
- vmax = max(vmax, v[i]);
- for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
- int m = t + vmax * vmax;
- f[0] = g[0] = 0;
- for (int i = 1; i <= m; i++) f[i] = g[i] = inf;
- for (int i = 1; i <= n; i++) for (int j = 0; j < v[i]; j++) {
- head = tail = 0;
- for (int k = 0, now; (now = k * v[i] + j) <= m; k++) {
- int tmp = f[now] - k;
- while (head < tail && que[tail - 1] > tmp) tail--;
- while (head < tail && id[head] < k - c[i]) head++;
- que[tail] = tmp;
- id[tail++] = k;
- f[now] = min(inf, que[head] + k);
- }
- }
- for (int i = 1; i <= n; i++) for (int j = 0; j < v[i]; j++) {
- int Min = inf;
- for (int k = j; k <= m; k += v[i]) {
- Min = min(Min, g[k] - k / v[i]);
- g[k] = Min + k / v[i];
- }
- }
- int ans = inf;
- for (int i = t; i <= m; i++) ans = min(ans, f[i] + g[i - t]);
- printf("%d\n", ans == inf ? -1 : ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2294757.html