题解：P15436 [蓝桥杯 2025 国 Python B] 魔法护盾

· · 题解

题目描述很清楚，我就不赘述了。

考虑动态规划。

状态就设的直白一点，设 dp_j 表示使用 j 次护盾增幅的最大护盾值。

初始化就是 dp_0=b。

那转移方程就很好写了，分为两种：

  1. 不使用护盾增幅，那我们的 dp_j 就可以直接从 dp_j+s_i 转移过来。
  2. 使用护盾增幅，那 dp_j 就需要从 dp_{j-1}+2 \times s_i 转移过来。

注意过程对 c 取 \min。

但是，我们考虑到，目前在第 i 关，若 dp_j<a_i 就证明 dp_j 已经无效了，就可以把 dp_j 设为负无穷。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,c,b,s[N],a[N],dp[N],ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>c>>b;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[0]=b; 
    for(int i=1;i<=n;i++){
        int sum=9e18;
        for(int j=i;j>=0;j--){
            dp[j]=min(dp[j]+s[i],c);
            if(j!=0) dp[j]=max(min(dp[j-1]+2*s[i],c),dp[j]);
            if(dp[j]>=a[i]) sum=min(sum,j);
            else dp[j]=-1e9;
        }
        ans=max(ans,sum);
        if(ans==9e18){
            cout<<-1;
            return 0;
        }
    }
    cout<<ans;
    return 0;
}

:::info[一种错误的做法。] 这道题我一开始拿贪心做的，代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=10100;
int n,c,b,s[N],a[N],ans;
priority_queue <int> pq;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>c>>b;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    int sum=b,vis=1;
    for(int i=1;i<=n;i++){
        if(s[i]>0) pq.push(s[i]);
        sum+=s[i],sum=min(sum,c);
        while(sum<a[i]&&!pq.empty()){
            int t=pq.top();
            pq.pop();
            sum+=t,sum=min(sum,c);
            ans++;
        }
        if(sum<a[i]){
            vis=0;
            break;
        }
    }
    if(!vis) cout<<-1;
    else cout<<ans;
    return 0;
}

但其实这是错误的。

这个贪心相当于是一个反悔贪心，跳到之前的关卡使用护盾增幅。

问题很明显，我们不知道当时的关卡使用护盾增幅之后的护盾有没有超过 c。 :::

感谢观看！