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

题意大意

有

N

种饮料，第

i

种饮料价值

c_i

花费

l_i

，求在每种饮料只买一种且总花费大等于

L

的情况下最小价值。

题目思路

这道题可以用动态规划的刷表法写。
刷表法：由当前点的状态，更新其他点的状态。
需要注意：只用当每个状态所依赖的状态对它的影响相互独立。

代码实现

f_{i,j}

代表买

i

种饮料，总容量为

j

毫升的最小花费。但是题目说总容量大于等于

L

即可，所以我们要将

j+l_{i+1}

大于等于

L

的情况存

f_{i+1,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;
}

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

文章操作

题意大意

题目思路

代码实现

代码

相关推荐

评论

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