题解：CF1989D Smithing Skill

FYS_ZBC · 2025-12-18 09:19:09 · 题解

CF1989D Smithing Skill

题意

给定 n 个武器，制造一把第 i 武器需要 a_i 个同种材料，熔毁一把第 i 种武器可返还 b_i 个与制造时同种的材料，每次制造和熔毁操作都会获得 1 点经验值。

同时给定 m 种材料，第 i 种材料有 c_i 个。

求你能用这 m 种材料进行制造和熔毁能获得的最大经验值。

思路

首先考虑贪心，锻造一把武器之后立刻熔毁，肯定是最优的。对于第 i 把武器，这次操作会花费 a_i-b_i 个同种原料，我们优先选择 a_i-b_i 尽量小的武器。

若通过花费最少的武器k进行若干轮操作后材料数 <a_k，我们此时则选取花费较多但 a_i 较小的武器进行操作。

但直接贪心复杂度会爆。因为不同原料之间相互独立，所以我们分开来考虑。对于所有 >10^6 的原料 c_i，可可以选取最优策略进行转移，最终 c_i 的范围将被缩小到 10^6。

那么我们再预处理出在 10^6 的范围内每个原料个数对答案的最大贡献 c_i，我们先处理出对于 i 可进行的最优操作消耗的原料个数 f_i，如果 f[i] 存在，即 i 还能被锻造成武器，则有 c_i=c_{i-f[i]}+1。

对于每一个材料 c_i，若 c_i \le 10^6 则直接查表即可，否则在进行若干最优转移后查表，时间复杂度 O(n)。

最后别忘了将 ans \times 2。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],b,f[N];
int c[N];
int s,n,m,y,ans;
signed main(){
    memset(f,0x3f,sizeof f);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s=max(s,a[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>b;
        f[a[i]]=min(f[a[i]],a[i]-b);
    }
    for(int i=1;i<=s;i++){
        f[i]=min(f[i],f[i-1]);
    }
    for(int i=1;i<=s;i++){
        if(i>=f[i])
        c[i]=c[i-f[i]]+1;
    }
    while(m--){
        cin>>y;
        if(y>s){
            int t=(y-s)/f[s]+1;
            y-=t*f[s];
            ans+=t;
        }
        ans+=c[y];
    }
    cout<<ans*2<<'\n';
}