题解：P16082 [ICPC 2024 NAC] Arrested Development

heffo_hard · 2026-05-09 20:19:04 · 题解

一眼 dp。\ 定义 dp_{i,j} 为考虑前 i 个任务，练习生一完成任务的时间不超过 j 时，练习生二的最短时间，于是我们可以得到以下转移方程：dp_{i,j}= \min (dp_{i-1,j}+b_i,dp_{i-1,j-a_i})，如果 j<a_i 则 dp_{i,j}=dp_{i-1,j}+b_i。
注意到这样写内存不够，会 MLE，于是我们考虑用滚动数组优化，这时的代码就足以通过此题。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f
const int MAXN=10000005;
int n;
int a[MAXN],b[MAXN],dp[MAXN],w,ans=inf;
signed main(){
    scanf("%lld",&n);
    //dp[i][j]:处理前i个任务，A用j分钟，B的最短时间
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&a[i],&b[i]);
        w+=max(a[i],b[i]);//用于求最大时间
    }
    for(int i=1;i<=n;++i){
        for(int j=w;j>=0;--j){
            if(j<a[i])dp[j]+=b[i];
            else dp[j]=min(dp[j]+b[i],dp[j-a[i]]);
        }
    }
    for(int i=0;i<=w;++i)ans=min(ans,max(i,dp[i]));
    printf("%lld",ans);
    return 0;
}

如果对您有帮助，可以点个赞吗？