D. Make Them Equal

D. Make Them Equal

【题目大意】
你有一个长度为 nn，初始全为 1 的数组 a，和两个长度为 n 的数组 b,c。你可以最多进行 k次如下的操作：选择两个正整数 i,x，使ai变成(ai+ai/x)，下取整。最后如果ai = bi，就可以获得ci的收益。要求最大化收益。

这题是一个预处理的01背包。难在预处理上。
起初我的代码是每次让a*=2，算出每个a的最小操作次数，再使用01背包获得最大收益，但写完发现比如数字31,如果从6开始以2倍增，那么增加到24时，与31相差7， 但这时24除以谁也不会得到7，即x无法取值，所以贪心有问题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>#define ft first
#define sd second
#define pb push_back
using namespace std;typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef map<int, int> MPII;
typedef map<LL, LL> MPLL;const int N = 3e6 + 10;int a[N], b[N], c[N], cost[N];
int main()
{for (int i = 0; i <= 1010; i++)cost[i] = 0x3f3f3f3f;cost[1] = 0;int ll = 1;cost[2] = 1;cost[3] = 2;// 动态更新每个值，有前面的更新后面的// 如 i+i/j=31时，在i=25的时找到， 在i=26 i = 27....都能找到// 但是我们为了取更小操作数，直接取cost[25]+1， 一步到位for (int i = 2; i <= 31; i++){for (int j = 1; j <= i; j++){// cout << "i = " << i << ", j = " << j << ", i+i/j = " << i + i / j << ", cost[i+i/j] = " << cost[i + i / j] << ", cost[i] = " << cost[i] << endl;cost[i + i / j] = min(cost[i + i / j], cost[i] + 1);}}cost[31] = 1;cost[1] = 0;int t;cin >> t;while (t--){int n, k;cin >> n >> k;for (int i = 0; i <= 1e6 + 10; i++)a[i] = 0;for (int i = 1; i <= n; i++)cin >> b[i];for (int i = 1; i <= n; i++)cin >> c[i];for (int i = 1; i <= n; i++)b[i] = cost[b[i]];for (int i = 1; i <= n; i++){for (int j = k; j >= b[i]; j--){if (a[j] < a[j - b[i]] + c[i])a[j] = a[j - b[i]] + c[i];}}cout << a[k] << endl;}return 0;
}