参考: DP
#include <iostream>
#include <algorithm>
#include <cstring>
const int N = 210, M = 20010;
int n, m;
int w[N], s[N];
int dp[M];
struct Node{
int ans, W;
}q[M];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
scanf("%d", &m);
memset(dp, 0x3f3f3f3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < w[i]; j ++ ) { // j为模w[i]后的余数
int head = 1, tail = 0;
for (int k = j, cnt = 0; k <= m; cnt ++ , k += w[i]) {
if (tail - head == s[i]) head ++ ;
int ans = dp[k] - cnt;
while (head <= tail && ans < q[tail].ans) tail -- ;
q[++ tail].ans = ans, q[tail].W = k;
dp[k] = q[head].ans + cnt; //转移当前的最新状态
}
}
printf("%d\n", dp[m]);
return 0;
}