首页
登录 | 注册

潜水员的问题

 [POI1998] 潜水员的问题

★★   输入文件:ple.in   输出文件:ple.out   简单对比
时间限制:1 s   内存限制:128 MB

【问题描述】

    一个潜水员在潜水时使用一种特殊的装置:一个有两个容器的气筒。一个容器中装的是氧气,另一个容器中装氮气。潜水员需要携带的氧气和氮气量依赖于潜水的时间和深度。潜水员有一系列的气筒,用来在不同的情况下携带。每个气筒可以用这样几个量来描述:气筒的质量,气筒中所能容纳的氧气量,以及可以容纳的氮气量。为了能完成最近的一个任务,潜水员需要一定量的氧气和氮气。潜水员有一系列准备好的气筒。他希望能携带总质量尽可能小的气筒下水。现在请你帮他计算一下至少要携带多少质量的气筒下水才能完成这个任务。

【示例说明】

    潜水员有以下 5 个气筒。每个气筒用三个整数来描述:气筒所能容纳的氧气的量,氮气的量和气筒的质量:

3 36 120 
10 25 129 
5 50 250 
1 45 130 
4 20 119

    如果这次任务中潜水员需要携带 5 升 氧气, 60 升 氮气。那么他至少要携带总质量为 249 的气筒下水(样例中的第一个和第二个气筒或者第四个和第五个气筒)。

【任务】

写一个程序:

•  从输入文件中读入完成任务所需要的氧气和氮气量以及气筒的个数和对每个气筒的描述。

•  计算潜水员完成任务至少需要携带的多少质量的气筒。

•  将结果写入输出文件中。

注意:题目中给出的气筒总是能够容纳足够多的气体使得潜水员能完成任务。

【输入格式】

    在文件的第一行中有两个整数 t 和 a ,分别描述完成任务所需的氧气和氮气量。( 1 ≤ t ≤ 21 , 1 ≤ a ≤ 79 )。第二行中有一个整数 n ,表示气筒的个数。( 1 ≤ n ≤ 1000 )。以后 n 行中,每行有三个整数 t i , a i , w i , t i 表示第 i 个气筒所能容纳的氧气量, a i 表示第 i 个气筒所能容纳的氮气量, w i 表示气筒 i 的质量。( 1 ≤ a i ≤ 21 , 1 ≤ t i ≤ 79 , 1 ≤ w i ≤ 800 )。

【输出格式】

    输出文件只有一行,这行中包含一个整数,表示最少需要携带的多少质量的气筒来完成改任务)。

【样例输入】

ple.in

5 60 

3 36 120 
10 25 129 
5 50 250 
1 45 130 
4 20 119

【样例输出】

ple.out

249


/****
01背包问题,
本题要满足的条件有两条:氮气要足量并且氧气也要足量。
因此,我们可以用三维数组dp[i][j][k],但可能会出现数组越界:

    按照01背包状态压缩的思想,当前物品的最优解是由上一件物品的最优解推出,这样可以将状态压缩为二维,
复杂度也会降低,变成O(n^2);
    接着,如果dp[j+t[i]][k+a[i]]中,j+t[i]>T(就是题目给的t),或者,k+a[i]>A(题目给的a),这就相当于超出
规定范围,因此,不需要具体知道超出的氧气量和氮气量的数字,直接以T和A代替即可。此时,dp的大小就变成了
T*A。空间也就节约了,算法的复杂度变成了O(T*A)。

****/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

int T,A,n;
int t[1001],a[1001],w[1001];
long long dp[22][80]={0};

int f(int a,int b,int c)
{
    if(a+b<=c)
        return a+b;
    else
        return c;
}

void read()
{
    freopen("ple.in","r",stdin);
    freopen("ple.out","w",stdout);
    int i;
    scanf("%d%d%d",&T,&A,&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d",&t[i],&a[i],&w[i]);
    }
}

void DP()
{
    int i,j,k;
    for(j=T;j>=0;j--)
        for(k=A;k>=0;k--)
            dp[j][k]=10000000;
    dp[0][0]=0;
    for(i=0;i<n;i++)
    {
        for(j=T;j>=0;j--)
            for(k=A;k>=0;k--)
        {
                int temp=w[i]+dp[j][k];
                int J=f(j,t[i],T),K=f(k,a[i],A);  //将超过T或A的全部变成T和A
                if(temp<dp[J][K])
                dp[J][K]=temp;
        }
    }
}

void print()
{
    printf("%lld\n",dp[T][A]);
}

int main()
{
    read();
    DP();
    print();
    return 0;
}




2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号