1 /**\ 2 https://codeforces.com/problemset/problem/1633/D 3 注意到b[i]的范围最大是 1000 ,从1-1000 变化最多大约在13次左右 4 13n复杂度不高,直接预处理每个数从1-1000变化花费 5 然后经典01背包 6 \**/ 7 #include <bits/stdc++.h> 8 using namespace std; 9 #define int long long 10 #define sf(x) scanf("%lld",&x) 11 #define ytz int _; sf(_); while(_--) 12 #define go continue 13 #define fory(i,a,b) for(int i = a; i <= b; ++i) 14 #define forl(i,a,b) for(int i = a; i >= b; --i) 15 #define debug(a) cout<<#a<<" = "<<a<<endl; 16 const double eps = 1e-7, pi = acos(-1.0); 17 18 const int N = 2e3 + 10; 19 const int M = 1e6 + 10; 20 21 int n, k; 22 int b[N], c[N], f[M], cost[N]; 23 24 void solve() 25 { 26 sf(n), sf(k); 27 k = min(13 * n, k); 28 fory(i, 1, n) sf(b[i]); 29 fory(i, 1, n) sf(c[i]); 30 31 memset(f, 0, sizeof f); 32 33 fory(i, 1, n) 34 { 35 int cc = cost[b[i]]; 36 for(int j = k; j >= cc; --j) 37 { 38 f[j] = max(f[j], f[j - cc] + c[i]); 39 } 40 } 41 printf("%lld\n", f[k]); 42 } 43 44 signed main() 45 { 46 memset(cost, 0x3f, sizeof cost); 47 cost[1] = 0; 48 fory(i, 1, 1000) 49 { 50 for(int j = 1; j <= i; ++j) 51 { 52 int tmp = i / j; 53 if(i + tmp <= 1000) cost[i + tmp] = min(cost[i + tmp], cost[i] + 1); 54 } 55 } 56 ytz 57 { 58 solve(); 59 } 60 return 0; 61 }