专栏文章

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

CClouds_dream
B3873题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mip63afa
此快照首次捕获于
2025/12/03 06:46
3 个月前
此快照最后确认于
2025/12/03 06:46
3 个月前
查看原文

前置知识

01背包——OI wiki

题目大意

题目传送门

题目分析

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

优化

第一，如果 li>Ll_i>L ,我们就可以把 lil_i 设为 LL ,避免超时（剪枝优化）。
第二，我们可以发现背包的容量为 2L−12L-1 ,并且如果选择出来的物品的 lil_i 之和大于 2L2L ,那它一定不是最优方案。

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

  1. 假设存在最优解 S∗≥2LS^*\geq 2L
    设 S∗S^* 是最优解的总容量，且 S∗≥2LS^*\geq 2L ，对应的最小花费为 C∗C^* 。
  2. 移除部分物品
    由于每个物品的容量 li≤Ll_i\leq L （经过剪枝优化），我们可以从 S∗S^* 中逐个移除物品，直到剩余容量 S′S' 满足 S′<2LS'<2L 。
    移除过程中，剩余容量始终 ≥L\geq L （初始 S∗≥2LS^* \geq 2L ，每次移除物品 li≤Ll_i \leq L ，故 S∗−li≥2L−L=LS^* - l_i \geq 2L - L = L ）。
  3. 花费对比
    设移除物品后的总花费为 C′C' ，则：
    C′≤C∗−∑removedci≤C∗C' \leq C^* - \sum_{\text{removed}} c_i \leq C^*
    所以不等号成立：因 ci≥0c_i \geq 0 （物品花费非负），移除物品不会增加花费。
  4. 剩余容量范围
    移除过程结束时：
    S′∈[L, 2L−1] （因 S′<2L 且 S′≥L）S' \in [L,\, 2L-1] \quad \text{ （因 $S' < 2L$ 且 $S' \geq L$）}
  5. 推出矛盾
    • C′≤C∗C' \leq C^* 且 S′≥LS' \geq L ，说明 S′S' 是一个合法解。
    • 但 C′≤C∗C' \leq C^* 与 "C∗C^* 是最小花费"矛盾（若 C′<C∗C' < C^* ，则 C∗C^* 非最优；若 C′=C∗C' = C^* ，则 S′S' 是更优解，因其容量更接近 LL ）。
故结论得证。

继续分析

然后我们就可以按照上面的思路开始 DP 了，然后从 LL 到 2L−12L-1 遍历一下 dpdp 数组，然后 dpidp_i 的最小值就是答案。
无解情况：
  1. ∑i=1nli<L\sum_{i=1}^{n}l_i<L ,即 所有饮料之和都不能满足需求，就输出 no solution 。
  2. 把 ansans 初始化为一个大值，如果遍历完 dpdp 数组 ansans 仍为最大值，则也无解。
还有，注意 dpdp 数组要初始为一个大值。

答疑

Q：为什么要从 LL 遍历到 2L−12L-1 ？
A：因为只有大于等于 LL 的方案才合法，并且对于以下数据来说
CPP
5 100
1 2000
10 100
20 80
40 20
10000 1
购买的饮料总容量可能大于 LL ，这种情况下如果写 LL 不能覆盖到全部，但写 2L2L 就可以。

代码实现

CPP
#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⁡\min 函数写法不当的问题。
2025/6/2 证明了背包容量为 2L−12L-1 。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...