题目
你有一个大小为 n 的整数数组。 最初，a数组的所有元素都等于1。可以执行以下操作：选择两个整数i（1≤i≤n）和x（x>0），然后将ai的值增加⌊aix⌋（ 即使 ai=ai+⌊aix⌋)。
执行完所有操作后，您将收到 ai=bi 的所有 i 的 ci 币。
您的任务是通过执行不超过 k 个操作来确定您可以接收的最大硬币数量。
n <= 1e3
bi >= 1
bi <= 1e3
k <= 1e6
题解思路
因为b数组的值都比较小，我们可以先预处理出从1到达每个比1000小的数的最小操作数，这里用的是线性dp。
剩下的基本上就是01背包优化内存的模板了。
这里时间复杂度（nk） 1e9 就是硬跑过去了。非常神奇。
AC代码
#include //#include //priority_queue#define PII pair#define ll long longusing namespace std;const int INF = 0x3f3f3f3f;const int N = 1000100;int a[N] ; int b[N] ;int f[N] ; int dp[N] ; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); memset(f,0x3f,sizeof(f) ) ; f[1] = 0 ; for (int i = 1 ; i <= 1000 ; i++ ) for (int j = 1 ; j <= i ; j++ ) { int sk = i + i/j ; f[sk] = min(f[sk],f[i]+1) ; } int T ; cin >> T ; while ( T-- ) { int n , k ; cin >> n >> k ; for (int i = 1 ; i <= n ; i++ ) cin >> a[i] ; for (int i = 1 ; i <= n ; i++ ) cin >> b[i] ; for (int i = 0 ; i <= k ; i++ ) dp[i] = 0 ; for (int i = 1 ; i <= n ; i++ ) for (int j = k ; j >= f[a[i]] ; j-- ) dp[j] = max(dp[j],dp[j-f[a[i]]] + b[i]); cout << dp[k] << "n" ; } return 0 ;}