题解：B3873 [GESP202309 六级] 小杨买饮料

· · 题解

前置知识

01背包——OI wiki

题目大意

题目传送门

题目分析

有 N 个物品，每个物品的价值为它的容量 l_i ，价值为它的售价 c_i ，求在容量不小于 L 的情况下花费的最小值。如果我们直接用转移方程的板子 dp_j=\min(dp_j,dp_{j-l_i}+c_i) 的话会超时，因为 l_i 非常大，可达 10^6 ,所以我们必须考虑优化。

优化

第一，如果 l_i>L ,我们就可以把 l_i 设为 L ,避免超时（剪枝优化）。

第二，我们可以发现背包的容量为 2L-1 ,并且如果选择出来的物品的 l_i 之和大于 2L ,那它一定不是最优方案。

证明背包容量为 2L-1 （反证法）

  1. *假设存在最优解 $S^\geq 2L** 设 S^ 是最优解的总容量，且 S^\geq 2L ，对应的最小花费为 C^*$ 。

  2. 移除部分物品
    由于每个物品的容量 l_i\leq L （经过剪枝优化），我们可以从 S^* 中逐个移除物品，直到剩余容量 S' 满足 S'<2L 。
    移除过程中，剩余容量始终 \geq L （初始 S^* \geq 2L ，每次移除物品 l_i \leq L ，故 S^* - l_i \geq 2L - L = L ）。

  3. 花费对比
    设移除物品后的总花费为 C' ，则：

    C' \leq C^* - \sum_{\text{removed}} c_i \leq C^*

    所以不等号成立：因 c_i \geq 0 （物品花费非负），移除物品不会增加花费。

  4. 剩余容量范围
    移除过程结束时：

    S' \in [L,\, 2L-1] \quad \text{ （因 $S' < 2L$ 且 $S' \geq L$）}

  5. 推出矛盾

    • 但 C' \leq C^* 与 "C^* 是最小花费"矛盾（若 C' < C^* ，则 C^* 非最优；若 C' = C^* ，则 S' 是更优解，因其容量更接近 L ）。

故结论得证。

继续分析

然后我们就可以按照上面的思路开始 DP 了，然后从 L 到 2L-1 遍历一下 dp 数组，然后 dp_i 的最小值就是答案。

无解情况：

  1. 所有饮料之和都不能满足需求，就输出 ```no solution``` 。

  2. 把 ans 初始化为一个大值，如果遍历完 dp 数组 ans 仍为最大值，则也无解。

还有，注意 dp 数组要初始为一个大值。

答疑

Q：为什么要从 L 遍历到 2L-1 ？

A：因为只有大于等于 L 的方案才合法，并且对于以下数据来说

5 100
1 2000
10 100
20 80
40 20
10000 1

购买的饮料总容量可能大于 L ，这种情况下如果写 L 不能覆盖到全部，但写 2L 就可以。

代码实现

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define TRACE 1
#define tcout TRACE && cout

#define int long long
//十年OI一场空，不开long long见祖宗（其实本题没必要）

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//快读

#define pri priority_queue
const int P = 998244353;
const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1e6+10, M = 1e8 + 10;

int n,L;//n为物品数量，L为需要的数量
int c[N],l[N];//含义见题目
int dp[N];
int cnt=0;//饮料总量

signed main()
{
    fst
    memset(dp,0x3f,sizeof(dp));//数组初始化
    cin>>n>>L;
    for(int i=1;i<=n;i++){
        cin>>c[i]>>l[i];
        cnt+=l[i];
        l[i]=min(l[i],L);
    }
    if(cnt<L){
        cout<<"no solution";//无解1
        return 0;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=2*L;j>=l[i];j--){
            dp[j]=min(dp[j],dp[j-l[i]]+c[i]);//板子
        }
    }
    int ans=INF;
    for(int i=L;i<=2*L;i++){
        ans=min(ans,dp[i]);
    }
    if(ans==INF){
        cout<<"no solution";//无解2
        return 0;
    }
    cout<<ans;
    return 0;
}

UPD

2025/6/2 改正了 \min 函数写法不当的问题。

2025/6/2 证明了背包容量为 2L-1 。