D. Make Them Equal edu122 div2

Equal edu122 div2"/>

D. Make Them Equal edu122 div2

Problem - D - Codeforces

题意是给你一个长度为n的初始值为1的序列。再给你一个b序列，每一次操作可以是(下取整)，最多k次操作，如果a[i]==b[i]，则有c[i]的贡献，问最大的价值是多少

分析：

可以把问题转化，如果可以到目标的b[i]的值需要使用多少次k，因为都是从1开始的。所以可以把问题转化成一共有容量是k的背包，往里面塞物品，每个物品的体积是之前预处理出来的最小步数（就是从1开始到b[i]最少用的次数），每个物品的价值是c[i]，这样就可以转化成一个01背包的问题了。

至于预处理，可以使用bfs，因为b[i]很小。

（有一说一，bfs我真的好久好久没写过了，平时还要加强算法的训练呐）

下面看代码就可以：

有一些细节再注意一下就好啦：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e18,mod=998244353;
int dist[N],f[N];
int n,k;
int a[N],b[N];
void bfs()
{memset(dist,0x3f,sizeof(dist));queue<int> q;dist[1]=0;q.push(1);while(q.size()){auto t=q.front();q.pop();for(int i=1;i<=t;i++){int x=t+t/i;if(x>1000) continue;if(dist[x]>dist[t]+1){dist[x]=dist[t]+1;q.push(x);}} }
}
signed main(){IOS;int T;//T=1;cin>>T;bfs();while(T--){int sum=0;cin>>n>>k;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){cin>>a[i];a[i]=dist[a[i]];sum+=a[i];}for(int i=1;i<=n;i++) cin>>b[i];sum=min(sum,k);for(int i=1;i<=n;i++){for(int j=sum;j>=a[i];j--)f[j]=max(f[j],f[j-a[i]]+b[i]);}cout<<f[sum]<<"\n";}return 0;
} 
/**/