优化代码#include<bits/stdc++.h> using ll=long long; const int maxn=1e3+1e2; const int inf=1e3; int step[maxn]; void init(){ std::queue<int>q; step[0]=1; q.push(1); while(!q.empty()){ int y=q.front();q.pop(); for(int x=1;x<=y;x++){ int ny=y+(y/x); if(step[ny]||ny>inf){ continue; } step[ny]=step[y]+1; q.push(ny); } } } void solve() { int n,k;std::cin>>n>>k; std::vector<int>b(n),c(n); for(auto&i:b)std::cin>>i; for(auto&i:c)std::cin>>i; std::vector<int> dp(maxn*maxn); for(int i=0;i<n;i++){ for(int j=k;j>=step[b[i]];j--){ dp[j]=std::max(dp[j],dp[j-step[b[i]]]+c[i]); } } std::cout<<dp[k]<<'\n'; } int main() { init(); std::cin.tie(nullptr)->sync_with_stdio(false); int t;std::cin>>t; while(t--)solve(); return 0; }

这段代码是一个背包问题的动态规划实现，使用了队列和BFS来预处理每个可达的状态的步数，并且使用了滚动数组来压缩空间。具体来说，对于每个物品i，从k到step[b[i]]的背包容量进行逆序遍历，更新dp[j]的值为dp[j-step[b[i]]]+c[i]和dp[j]的较大值，其中c[i]表示第i个物品的价值，b[i]表示第i个物品的体积。

需要注意的是，这段代码可能存在一些隐患，如未对输入的数据进行判断和处理，会导致数组越界等问题。另外，也可以使用更加规范的头文件和命名空间，避免出现一些不必要的错误。