题解：P10987 [蓝桥杯 2023 国 Python A] 火车运输

yechenguo · 2024-08-29 21:33:25 · 题解

这道题是 01 背包变形。

在看完这道题的时候，思路特别清晰，除了这里的价值和质量是一个东西，这不就是 01 背包变成二维了吗？没什么难度啊？

于是，就有了这段代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,w[2005],dp[2005][2005],maxx;
signed main()
{
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=a;j>=w[i];j--)
            for(int k=b;k>=w[i];k--)
            {
                dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+w[i]);
                dp[j][k]=max(dp[j][k],dp[j][k-w[i]]+w[i]);
                maxx=max(maxx,dp[j][k]);
            }
    cout<<maxx;
    return 0;
}

只有 5 分。

经过一段苦思冥想后，我再次茅塞顿开。这道题的 j 和 k 不能直接到 w_i 就结束了，因为如果这样，那有可能有些下标会更新不到。比如，如果 w_i 没有 0 那么 dp_{w_i,0} 等就会更新不到，会影响结果，所以，j 和 k 要取到 0。

最后，上代码！！！

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,w[2005],dp[2005][2005],maxx;
signed main()
{
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++)
        for(int j=a;j>=0;j--)
            for(int k=b;k>=0;k--)
            {
                if(j>=w[i]) dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+w[i]);
                if(k>=w[i]) dp[j][k]=max(dp[j][k],dp[j][k-w[i]]+w[i]);
                maxx=max(maxx,dp[j][k]);
            }
    cout<<maxx;
    return 0;
}