抢修计划

【题意简述】

有 $n$ 个依次开放的区域。区域 $1$ 始终可以抢修；只有区域 $1,2,\ldots,i-1$ 均至少抢修过一次，区域 $i$ 才能被抢修。首次抢修区域 $i$ 获得 $a_i$，以后每次获得 $b_i$。最多进行 $k$ 次行动，求最大总价值。

【Hint】

【提示】

假设最终只开放到区域 $i$。前 $i$ 个区域必须各完成一次首次抢修，剩余行动全部放在 $b_j$ 最大的已开放区域上。

【数据点 1∼51\sim 51∼5】

当 $n,k\leq 10$ 时，可以把一次抢修看成搜索树的一层。状态记录各区域已经抢修的次数，枚举当前已经开放的区域作为下一次选择。同一状态只保留已经得到的最大价值，搜索深度不超过 $k$。

这一做法完整枚举了全部合法行动序列，可以作为后续结论的直接验证。

【数据点 6∼106\sim 106∼10】

假设最后开放到区域 $i$。区域 $1,2,\ldots,i$ 都必须完成一次首次抢修，所以已经消耗 $i$ 次行动，得到

剩余 $k-i$ 次行动不会再改变开放范围。每次都选择 $b_j$ 最大的已开放区域一定最优，因此候选答案为

直接枚举 $i$ 并重新计算前缀最大值，时间复杂度为 $\mathcal{O}(n^2)$。

【数据点 11∼1511\sim 1511∼15】

特殊性质保证 $b$ 单调不降。最后开放到区域 $i$ 时，已经开放区域中的最大重复抢修价值就是 $b_i$，于是候选答案变为

顺序维护 $a$ 的前缀和即可在线性时间完成这一档。

【正解】

定义

最后开放到区域 $i$ 时，最优价值为

其中 $1\leq i\leq\min(n,k)$。

必要性是显然的：想要开放区域 $i$，必须依次完成前 $i$ 个区域的首次抢修，因此前 $i$ 次行动的总价值固定为 $A_i$；剩余每次行动的价值不超过 $B_i$。

充分性同样成立：依次完成前 $i$ 个区域的首次抢修，再把剩余 $k-i$ 次行动全部放在某个取得 $B_i$ 的区域上，恰好得到上述价值。因此枚举 $i$ 已经覆盖全部最优方案。

顺序扫描时同时维护 $A_i,B_i$，对每个合法的 $i$ 更新答案即可。

【复杂度分析】

时间复杂度为 $\mathcal{O}(n)$，空间复杂度为 $\mathcal{O}(n)$。总价值需要使用 long long。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/304Name:repair.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 20001011using namespace std;12 13int c,T,n,k;14long long a[MAXN],b[MAXN];15 16void Solve(){17    scanf("%d%d",&n,&k);18    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);19    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);20    long long Ans=0,PreSum=0,Max=0;21    for(int i=1;i<=min(n,k);i++){22        PreSum+=a[i];23        Max=max(Max,b[i]);24        Ans=max(Ans,PreSum+1ll*(k-i)*Max);25    }26    printf("%lld\n",Ans);27}28 29int main(){30    scanf("%d%d",&c,&T);31    while(T-->0) Solve();32    return 0;33}