D. Make Them Equal(dp + 范围优化 )

Problem - 1633D - Codeforces

你有一个大小为n的整数数组a，初始时，数组中的所有元素都等于1，你可以进行以下操作：选择两个整数i（1≤i≤n）和x（x>0），然后将ai的值增加⌊aix⌋（即使ai=ai+⌊aix⌋）。

进行所有操作后，你将为所有ai=bi的这种i收到ci币。

你的任务是确定执行不超过k个操作所能得到的最大数量的硬币。

输入
第一行包含一个整数t（1≤t≤100）--测试案例的数量。

每个测试案例的第一行包含两个整数n和k（1≤n≤103；0≤k≤106）--分别是数组的大小和最大操作数。

第二行包含n个整数b1,b2,...,bn（1≤bi≤103）。

第三行包含n个整数c1,c2,...,cn（1≤ci≤106）。

所有测试案例的n之和不超过103。

输出
对于每个测试案例，打印一个整数--你通过执行不超过k个操作所能得到的最大硬币数。

例子
输入复制
4
4 4
1 7 5 2
2 6 5 2
3 0
3 5 2
5 4 7
5 9
5 2 5 6 3
5 9 1 9 7
6 14
11 4 6 2 8 16
43 45 9 41 15 38
输出拷贝
9
0
30
167
题解:
首先我们要考虑每个1最少要经过几步才能够到b[i],这其实也是个dp

由于n只有1000,直接枚举1000内所有i

转移方程为

注意初始化

    if(i + i/j <= 1000)
     {
             v[i + i/j] = min(v[i + i/j] ,v[i] + 1);
     }

 剩下其实就是一个01背包,k内范围如何得到最多代价,但是k有点大有1e6(CF平台有点nb,这1e3*1e6都能跑完)

但我们还是想想如何优化吧,仔细看看我们发现v[i]最大值不超过13,所以我们直接

k = min(k,n*13)比n*13大的是不需要的

这样我们时间复杂度就成了1e3*1e4

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
int b[1004];
int c[1004];
int v[1004];
int dp[1000040];
void solve()
{
	int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> b[i];
	}
	for(int i = 1;i <= n;i++)
	cin >> c[i];
	for(int i = 0;i <= k;i++)
	dp[i] = 0;
	k = min(k,n*13);
 	for(int i = 1;i <= n;i++)
	{
		for(int j = k;j >= v[b[i]];j--)
		{
			dp[j] = max(dp[j],dp[j - v[b[i]]] + c[i]);
		}
	}
	cout<< dp[k] << "\n";
	
}
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
	cin >> t;
	memset(v,0x3f,sizeof v);
	v[1] = 0;
	for(int i = 1;i <= 1000;i++)
	{
		for(int j = 1;j <= i;j++)
		{
			if(i + i/j <= 1000)
			{
				v[i + i/j] = min(v[i + i/j] ,v[i] + 1);
			}
		}
	}
	while(t--)
	{
		solve();
	}
}
 
//1 10 11
 
//001
//010
//011
//100