B3873 [GESP202309 六级] 小杨买饮料 题解
chenyv666
·
·
题解
题意大意
有 N 种饮料，第 i 种饮料价值 c_i 花费 l_i，求在每种饮料只买一种且总花费大等于 L 的情况下最小价值。
题目思路
这道题可以用动态规划的刷表法写。
刷表法：由当前点的状态，更新其他点的状态。
需要注意：只用当每个状态所依赖的状态对它的影响相互独立。
代码实现
买的话，先判断 $j+l_{i+1}$ 是否大于 $L$。如果小于 $L$ 就将 $f_{i+1,j+l_{i+1}}$ 设为买第 $i+1$ 个的情况和原来的 $f_{i+1,j+l_{i+1}}$ 值之间的最小值。否则就把它们之间的最小值存到 $f_{i+1,L}$。不买的话，将 $f_{i+1,j}$ 设为 $f_{i,j}$ 和
$f_{i,j}$ 之间的最小值。
最后判断 $f_{N,L}$ 是否被修改，进行输出。
## 代码
```cpp
//码风不好，请见谅
#include <bits/stdc++.h>
using namespace std;
int f[510][2010],c[510],l[510];
int main() {
int N,L;cin>>N>>L;
for(int i=1;i<=N;i++) cin>>c[i]>>l[i];
memset(f,0x3f,sizeof(f));f[0][0]=0;
for(int i=0;i<N;i++){
for(int j=0;j<=L;j++){
//刷表法
if(j+l[i+1]<L){
f[i+1][j+l[i+1]]=min(f[i][j]+c[i+1],f[i+1][j+l[i+1]]);//买
}else{
f[i+1][L]=min(f[i][j]+c[i+1],f[i+1][L]);//买
}
f[i+1][j]=min(f[i+1][j],f[i][j]);//不买
}
}
if(f[N][L]>=1e9){//判断值是否被修改
cout<<"no solution";
}else{
cout<<f[N][L];
}
return 0;
}
```