Codeforces 1633 D. Make Them Equal —— bfs，背包

This way

题意：

给你一个长度为n的数组a，一开始所有值都为1，你每次可以选择一个位置i，然后选择任意一个正整数x，使得$a[i]+=\lfloor \frac{a[i]}{x}\rfloor$。你最多执行k次操作，并且如果a[i]=b[i]的话，你会得到c[i]块钱，问你最后最多能有多少钱。

题解：

对于b的每个数字我们可以把它转换成至少要操作的次数，于是b和c变成了代价与价值，裸的背包。但是我们发现k是1e6诶，为何能背包。因为我猜测每个数最大转换次数不会超过20次，那么这就变成了2e4*1e3的背包，并且我使用了上下界优化。
那么怎么额找到操作次数呢？我一开始用二进制考虑，wa了。可能不能这么简单地贪心，那直接bfs搜索一下每个值需要的最少次数呗。这里我使用了整除分块，虽然加不加好像没什么区别。

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5,M=1e3+5;
int dp[N],b[M],c[M],step[M];
void init(){ 
   
    queue<int>Q;
    Q.push(1);
    while(!Q.empty()){ 
   
        int u=Q.front();Q.pop();
        for(int i=1;i<=u;){ 
   
            int ne=u+u/i;
            i=u/(u/i)+1;
            if(ne>=M||step[ne])continue;
            step[ne]=step[u]+1;
            Q.push(ne);
        }
    }
}
int main()
{ 
   
    init();
    int t;
    scanf("%d",&t);
    while(t--){ 
   
        int n,k,s=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]),b[i]=step[b[i]],s+=b[i];
        for(int i=1;i<=n;i++)scanf("%d",&c[i]);
        memset(dp,0,sizeof dp);
        if(s<=k){ 
   
            int ans=0;
            for(int i=1;i<=n;i++)ans+=c[i];
            printf("%d\n",ans);
            continue;
        }
        int r=0,ans=0;
        for(int i=1;i<=n;i++){ 
   
            r=min(k,r+b[i]);
            for(int j=r;j>=b[i];j--){ 
   
                dp[j]=max(dp[j],dp[j-b[i]]+c[i]);
                ans=max(ans,dp[j]);
            }

        }
        printf("%d\n",ans);
    }
    return 0;
}

今天的文章Codeforces 1633 D. Make Them Equal —— bfs，背包分享到此就结束了，感谢您的阅读。