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

约定不等于承诺〃 2024-03-31 14:42 66阅读 0赞

[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 <bits/stdc++.h>
    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.求最少步数应当想到最短路**

[Problem - D - Codeforces]: https://codeforces.com/contest/1633/problem/D