题解：P6715 [CCO 2018] Fun Palace

huangzixi071018 · 2025-10-16 20:35:39 · 题解

题目大意：

有 n-1 条边连接 i 到 i+1，当结点 i 的生物数量大于等于 a[i] 或结点 i+1 的生物数量大于等于 b[i] 时，这条边是生效的。注意当不满足以上条件的时候，那条边会自动失效。当结点 1 中有 e 个生物是出口会开，问最多能放置的生物数。

思路：

题目让人一眼看就是 DP，但也确实可以做。首先思考顺序，边联通两个点，是双向的，前面的结点可以走向后面的结点，来释放更多生物，因此要从前往后 DP。然后设计 dp，dp[i][j] 表示有 j 个生物可以跑到第 i 个结点的最大放置的生物数量。接下来分类去 dp，当 j\ge a[i]+b[i]时，可以先留 a[i] 个生物在 i 结点，其他结点跑到 i+1 结点，再让剩余的 a[i] 个通过，就相当于没有这条边的限制。当 j<a[i] 且 j<b[i] 时这条边不生效，所以答案可以直接加 j。最后最难的两种情况，当 j\ge a[i] 且不满足上面的情况时，这 j 个生物可以走 j-a[i] 个到 i+1，同理当 j\ge b[i]时，就可以有 i+1 结点的生物跑到 i 结点，直接加 b[i] 转移即可。

代码：

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5;
int a[N],b[N],dp[N][M];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,up=0;
    cin>>n>>m;
    up=m;
    for(int i=1;i<n;i++){
        cin>>a[i]>>b[i];
        up=max(up,a[i]+b[i]);
    }
    for(int i=0;i<m;i++){
        dp[1][i]=i;
    }
    for(int i=1;i<n;i++){
        int s=0;
        for(int j=0;j<up;j++){
            if(j>=a[i]+b[i]){
                dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
                continue;
            }
            if(j>=a[i]){
                dp[i+1][j-a[i]]=max(dp[i+1][j-a[i]],dp[i][j]);
            }
            if(j>=b[i]){
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-b[i]]+b[i]);
            }
            if(j<a[i]){
                s=max(s,dp[i][j]);
            }
        }
        for(int j=0;j<b[i];j++){
            dp[i+1][j]=max(dp[i+1][j],s+j);
        }
    }
    int ans=0;
    for(int i=0;i<up;i++){
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<"\n";
    return 0;
}