华师一附中OI组

标题: S2627潜水员 [打印本页]
作者: 叶梓文    时间: 2021-10-15 21:01
标题: S2627潜水员
题目：   
潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？
    例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119
    如果潜水员需要5升的氧和60升的氮则总重最小为249 （1，2或者4，5号气缸）。
    你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式
    从文本文件gas.in中读入数据。
    第一行有2整数t，a（1<=t<=21，1<=a<=79）。它们表示氧，氮各自需要的量。
    第二行为整数n （1<=n<=1000）表示气缸的个数。
    此后的n行，每行包括ti，ai，wi（1<=ti<=21，1<=ai<=79，1<=wi<=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。
输出格式
    仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
样例输入
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
样例输出

249






思路：
      经典01二维状态反背包问题。
      阶段：当收集了i体积的氧气和j体积的氮气所能达到的最小体积。
      状态：设dp[now][j]=k表示考虑到第now个气缸，已收集i体积的氧气和j体积的氮气时的最小体积为k，运用滚动数组将第一维压去，最终状态为dp[j]=k。
      转移：考虑第now个气缸选或不选，转移即为dp[j]=min(dp[j],dp[i-b[now].t][j-b[now].a]+b[now].w)。
注意：
      1.注意数组边界。
      2.注意初始状态和答案状态，该题中，初始状态：dp[0][0]=0，答案状态：for(int i=T;i<tt;i++)for(int j=A;j<aa;j++)ans=min(ans,dp[j])。
      3.注意对非法状态的表示，该题中，由于需取最小值，非法状态赋值为无穷大，即memset(dp,0x3f,sizeof(dp))，对于负无穷为memset(dp,0xcf,sizeof(dp))。
      4.01背包中使用滚动数组，倒序求解。
#include <bits/stdc++.h>
using namespace std;
const int tt=191,aa=129,nn=1011,inf=0x3f3f3f3f;
int T,A,n;
struct Node{
        int t,a,w;
}b[nn];
int dp[tt][aa],ans=inf;
int main(){
        cin>>T>>A>>n;
        for(int i=1;i<=n;i++){
                cin>>b.t>>b.a>>b.w;
        }
        memset(dp,0x3f,sizeof(dp));
        dp[0][0]=0;
        for(int now=1;now<=n;now++){
                for(int i=tt-1;i>=b[now].t;i--){
                        for(int j=aa-1;j>=b[now].a;j--){
                                dp[j]=min(dp[j],dp[i-b[now].t][j-b[now].a]+b[now].w);
                        }
                }
        }
        for(int i=T;i<tt;i++)for(int j=A;j<aa;j++)ans=min(ans,dp[j]);
        cout<<ans<<endl;
        return 0;
}



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2