codeforces-D. Make Them Equal (1600)

 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 
 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<<" = "<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 }