小杨买饮料 题解

本题是0/1背包的经典变形。将每种饮料视为一个物品，容量l_i为重量，费用c_i为价值，目标是从N种饮料中至多选择一种，使总容量至少达到L且总费用最小。关键在于容量要求是"至少为L"而非"恰好为L"，因此允许容量溢出。设dp[j]表示当前已选饮料总容量至少为j毫升时的最小费用，初始化dp[0]=0，其余dp[1...L]=INF（表示不可达）。对于第i种饮料，采用倒序循环j从L到1，确保每种饮料至多被选一次，这是0/1背包的标准处理方式。转移方程为dp[j] = min(dp[j], dp[max(j - l_i, 0)] + c_i)，其中max(j-l_i,0)巧妙处理了容量溢出：当j > l_i时，购买第i种饮料前需要满足j-l_i的容量要求，从dp[j-l_i]转移；当j <= l_i时，单瓶饮料已能满足至少j的容量，因此直接从dp[0]转移。DP完成后，若dp[L]仍为INF则说明所有饮料总容量不足L，输出"no solution"；否则输出dp[L]即为最少花费。时间复杂度O(N×L)，空间复杂度O(L)，均在题目限制范围内，可以顺利通过。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,l;
int c[2003],d[2003];
long long dp[2003];
int main(){
	cin>>n>>l;
    for(int i=1;i<=n;i++){
        cin>>c[i]>>d[i];
    }
    for(int i=1;i<=l;i++) dp[i]=N;
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=l;j>=1;j--){
            dp[j]=min(dp[j],dp[max(j-d[i],0)]+c[i]);
        }
    }
    if(dp[l]==N)  cout<<"no solution";
    else cout<<dp[l];
	return 0;
}