2019ICPCshenyang网络赛(C. Dawn-K's water)

简介: 2019ICPCshenyang网络赛(C. Dawn-K's water)

题目:

Dawn-K recently discovered a very magical phenomenon in the supermarket of Northeastern University: The large package is not necessarily more expensive than the small package.

On this day, Dawn-K came to the supermarket to buy mineral water, he found that there are nntypes of mineral water, and he already knew the price pp and the weight cc (kg) of each type of mineral water. Now Dawn-K wants to know the least money aa he needs to buy no less than mm kilograms of mineral water and the actual weight bb of mineral water he will get. Please help him to calculate them.

Input

The input consists of multiple test cases, each test case starts with a number nn (1 \le n \le 10^31≤n≤103) – the number of types, and mm (1 \le m \le 10^41≤m≤104) – the least kilograms of water he needs to buy. For each set of test cases, the sum of nn does not exceed 5e45e4.

Then followed n lines with each line two integers pp (1 \le p \le 10^91≤p≤109) – the price of this type, and cc (1 \le c \le 10^41≤c≤104) – the weight of water this type contains.

Output

For each test case, you should output one line contains the minimum cost aa and the weight of water Dawn-K will get bb. If this minimum cost corresponds different solution, output the maximum weight he can get.

(The answer aa is between 11 and 10^9109, and the answer bb is between 11 and 10^4104)

样例输入

3 3
2 1
3 1
1 1
3 5
2 3
1 2
3 3

样例输出

3 3
3 6

题意描述:这个题可以看成是一个完全背包的问题,就是要买满足至少m的水需要花费的最少钱是多少,其中n是水的种类,a[i]是水的价格,b[i]是以a[i]的价格买的水的重量。

程序代码:

#include<iostream>
#include<algorithm>
using namespace std;
long long mi=1e14;//表示样例所给的大小是10000
int a[1010],b[1010];
long long dp[50100];//给的样例是10^9,所以用long long
int main()
{
  int i,j,k,m,n,sum;
  long long x,y;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    sum=20010;
    for(i=0;i<n;i++)
      scanf("%d%d",&a[i],&b[i]);
    for(i=1;i<=sum;i++)
      dp[i]=mi;//定义最初的价格都是无穷大
    dp[0]=0;//买0需要花费0
    for(i=0;i<n;i++)
      for(j=b[i];j<=sum;j++)
      {
        dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
      }
    x=dp[m];
    y=m;
    for(i=m+1;i<=sum;i++)//寻找在sum和m之间是否还有满足的其价格更低
    {
      if(dp[i]<=x)
      {
        x=dp[i];
        y=i;
      }
    } 
    printf("%lld %lld\n",x,y);  
  }
  return 0;
}
相关文章
|
机器学习/深度学习 数据挖掘 数据库
7 Papers & Radios | ICLR 2022杰出论文奖;MIT将热光伏发电效率提到40%(1)
7 Papers & Radios | ICLR 2022杰出论文奖;MIT将热光伏发电效率提到40%
182 0
BUUCTF---misc---[ACTF新生赛2020]outguess
BUUCTF---misc---[ACTF新生赛2020]outguess
|
6月前
ZZULIOJ----2618: ACM-ICPC亚洲区域赛ZZUL
ZZULIOJ----2618: ACM-ICPC亚洲区域赛ZZUL
2022天梯赛三月冲刺——PAT (Advanced Level)1013 Battle Over Cities (并查集找连通块)
2022天梯赛三月冲刺——PAT (Advanced Level)1013 Battle Over Cities (并查集找连通块)
105 0
|
机器学习/深度学习 数据挖掘 数据库
7 Papers & Radios | ICLR 2022杰出论文奖;MIT将热光伏发电效率提到40%(2)
7 Papers & Radios | ICLR 2022杰出论文奖;MIT将热光伏发电效率提到40%
161 0
upc2021秋组队训练赛第一场 ICPC North Central NA Contest 2020
upc2021秋组队训练赛第一场 ICPC North Central NA Contest 2020
90 0
upc2021秋组队训练赛第一场 ICPC North Central NA Contest 2020
|
人工智能
upc 2021秋组队训练赛第三场 2020 Rocky Mountain Regional Contest
upc 2021秋组队训练赛第三场 2020 Rocky Mountain Regional Contest
95 0
CodeForces 1195D Submarine in the Rybinsk Sea (算贡献)
CodeForces 1195D Submarine in the Rybinsk Sea (算贡献)
68 0
AI:2020年6月22日北京智源大会演讲分享之11:30-12:20Jorge教授《Zero-Order Optimization Methods with Applications to RL》
AI:2020年6月22日北京智源大会演讲分享之11:30-12:20Jorge教授《Zero-Order Optimization Methods with Applications to RL》
AI:2020年6月22日北京智源大会演讲分享之11:30-12:20Jorge教授《Zero-Order Optimization Methods with Applications to RL》
|
传感器 编解码 算法
Google Earth Engine ——GCOM-C 进行长期和持续的全球叶面积指数数据集(JAXA/GCOM-C/L3/LAND/LAI/V1)
Google Earth Engine ——GCOM-C 进行长期和持续的全球叶面积指数数据集(JAXA/GCOM-C/L3/LAND/LAI/V1)
188 0
Google Earth Engine ——GCOM-C 进行长期和持续的全球叶面积指数数据集(JAXA/GCOM-C/L3/LAND/LAI/V1)