华师一附中OI组

标题: 潜水员 [打印本页]
作者: admin    时间: 2018-5-21 12:27
标题: 潜水员
潜水员为了潜水要使用特殊的装备。他有一个带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
作者: lyc    时间: 2018-5-21 13:35
dp
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cmath>
  5. const int oo = 0x3f3f3f3f;
  6. using namespace std;
  7. int o2[1010],n2[1010],w[1010];
  8. int dp[110][110];
  9. int ond, nnd;
  10. int n;
  11. int main()
  12. {
  13.     cin>>ond>>nnd;
  14.     cin>>n;
  15.     for(int i=1; i<=n; i++)
  16.     {
  17.         cin>>o2[i]>>n2[i]>>w[i];
  18.     }
  19.     for(int i=0; i<=100; i++)
  20.         for(int j=0; j<=100; j++)
  21.             dp[i][j] = oo;
  22.     dp[0][0] = 0;
  23.     for(int i=1; i<=n; i++)
  24.         for(int j=ond; j>=0; j--)
  25.             for(int k=nnd; k>=0; k--)
  26.             {
  27.                 int nowo = j + o2[i];
  28.                 int nown = k + n2[i];
  29.                 nowo = min(nowo, ond);
  30.                 nown = min(nown, nnd);
  31.                 dp[nowo][nown] = min(dp[nowo][nown], dp[j][k] + w[i]);
  32.             }
  33.     cout<<dp[ond][nnd];
  34.     return 0;
  35. }
复制代码
作者: admin    时间: 2018-5-21 22:47
学到了，楼上的LYC同学，你的那个oo变量定义的很有意思！！！！
作者: 张笑宇    时间: 2018-7-29 09:44
  1. #include<iostream>
  2. using namespace std;
  3. int sumv1,sumv2,n;
  4. const int mx=1010;
  5. int v1[mx],v2[mx],w[mx];
  6. int dp[mx][mx],i,j,k;
  7. int main()
  8. {
  9.     cin>>sumv1>>sumv2>>n;
  10.     for (i=1; i<=n; i++) cin>>v1[i]>>v2[i]>>w[i];
  11.     for (i=0;i<=sumv1;i++)
  12.         for (j=0;j<=sumv2;j++) dp[i][j]=9999999;
  13.     dp[0][0]=0;
  14.     for (i=1; i<=n; i++)
  15.         for (j=sumv1; j>=0; j--)///用的v1越来越少
  16.             for (k=sumv2; k>=0; k--)///v2越来越少
  17.             {
  18.                 int p1=min(j+v1[i],sumv1);///如果j+v1[i]超过了sumv1
  19.                 int p2=min(k+v2[i],sumv2);///就用sumv1代替
  20.                 dp[p1][p2]=min(dp[p1][p2],dp[j][k]+w[i]);
  21.             }
  22.     cout<<dp[sumv1][sumv2];
  23.     return 0;
  24. }
复制代码
作者: zhwang    时间: 2018-7-29 21:30
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. const int INF=999999999;
  5. int O2,N2;
  6. int n;
  7. int a[1001],b[1001];
  8. int w[1001];
  9. int f[101][101];
  10. int main()
  11. {
  12.         scanf("%d%d",&O2,&N2);
  13.         for(int i=0;i<=O2;i++)
  14.         {
  15.                 for(int j=0;j<=N2;j++)
  16.                 {
  17.                         f[i][j]=INF;
  18.                 }
  19.         }
  20.         f[0][0]=0;
  21.         scanf("%d",&n);
  22.         for(int i=1;i<=n;i++)
  23.         {
  24.                 scanf("%d%d%d",&a[i],&b[i],&w[i]);
  25.         }
  26.         for(int i=1;i<=n;i++)
  27.         {
  28.                 for(int j=O2;j>=0;j--)
  29.                 {
  30.                         for(int k=N2;k>=0;k--)
  31.                         {
  32.                                 int x=j+a[i];
  33.                                 int y=k+b[i];
  34.                                 if(x>=O2)
  35.                                 {
  36.                                         x=O2;
  37.                                 }
  38.                                 if(y>=N2)
  39.                                 {
  40.                                         y=N2;
  41.                                 }
  42.                                 f[x][y]=min(f[x][y],f[j][k]+w[i]);
  43.                         }
  44.                 }
  45.         }
  46.         /*for(int i=0;i<=O2;i++)
  47.         {
  48.                 for(int j=0;j<=N2;j++)
  49.                 {
  50.                         printf("%d ",f[i][j]);
  51.                 }
  52.                 printf("\n");
  53.         }*/
  54.         printf("%d",f[O2][N2]);
  55.         return 0;
  56. }
复制代码

这个题我已开始还以为是反过来求利润呢



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