Educational Codeforces Round 122 (Rated for Div. 2) D. Make Them Equal

Problem - D - Codeforces

题意：

给定三个数组a,b,c，其中a数组一开始为1，b和c数组是给定的。

对于每次操作，都可以选定一个i，任选一个x，使a[i]=a[i]+a[i]/x

操作最多执行k次

经过若干次操作后，若a[i]==b[i]，则可以获得c[i]的价值

问可以获得的最大价值是多少

思路：

有限制的价值问题，考虑做01背包

因此我们要去确定v[i]和w[i]的值

很显然在这道题中,w[i]=c[i]

因此我们去看v[i]的值，即a[i]从1变到b[i]的最少步数是多少

一开始想的是贪心，先一直取x=1，这样的话就相当于是二进制往上跳，但是这样的话，等我们跳到快超过b[i]的最后一步时，是否存在x使得a[i]+a[i]/x==b[i]这件事是难以判断的，因此这样的思路可以排除

因为要求最少步数，所以应该要想到求BFS最短路，而且这道题的数据范围很小，因此求最短路的思路更为合理

我们去预处理最短路数组dis，表示从1到b[i]的最短路的长度，这样v[i]的值就相当于是dis[b[i]]的值

求出v[i]之后去跑一边01背包即可

需要注意我们从1经过操作后变成b[i]的最少步数最多也就12步（二进制）,所以总操作步数取min(12*n,k)即可

这道题思路较为自然，但是最短路那一步还是没有想到

Code：

#include 
using namespace std;
#define int long long
const int mxn=1e3+10,mxe=2e5+10,mnf=1e18;
queue<int> q;
int n,k;
int b[mxn],c[mxn],dp[mxn*12],v[mxn],dis[mxn];
void solve(){
    memset(dp,0,sizeof(dp));
    cin>>n>>k;
    k=min(k,12ll*n);
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) v[i]=dis[b[i]];
    for(int i=1;i<=n;i++){
        for(int j=k;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
    }
    cout<<*max_element(dp,dp+1+k)<<'\n';
}
void init(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int x=1;x<=u;x++){
            int v=u+u/x;
            if(v<=1e3&&dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    init();
    while(T--)solve();
    return 0;
}

总结：

1.如果我们要去跑01背包的话，先去确定它v[i]和w[i]的值

2.求最少步数应当想到最短路