2019ACM-ICPC沈阳网络赛-C-Dawn-K's water（完全背包模板题）

Dawn-K's water

1000ms

262144K

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

Input

The input consists of multiple test cases, each test case starts with a number $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 $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

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

样例输入

样例输出

3 3
3 6

AC 代码：

 1 #include <bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn=1e6+7;
 6 const ll inf=0x3f3f3f3f3f;
 7 const int maxm=1e4;
 8 struct NODE
 9 {
10     ll wei;
11     ll val;
12 } node[maxn];
13 ll f[maxn];
14 template<class T>
15 inline void read(T &x)
16 {
17     T ans=0,f=1;
18     char ch=getchar();
19     while(ch>'9'||ch<'0')
20     {
21         if(ch=='-')f=-1;
22         ch=getchar();
23     }
24     while(ch<='9'&&ch>='0')
25     {
26         ans=ans*10+(ch-'0');
27         ch=getchar();
28     }
29     x=ans*f;
30 }
31 int main()
32 {
33     int n;
34     ll m;
35     while(~scanf("%d %lld",&n,&m))
36     {
37         for(register int i=1; i<=n; ++i)
38         {
39             read(node[i].val);
40             read(node[i].wei);
41         }
42         memset(f,inf,sizeof(f));
43         f[0]=0;
44         for(register int i=1; i<=n; ++i)
45         {
46             for(register int j=node[i].wei; j<=maxm; ++j)
47             {
48                 f[j]=min(f[j],f[j-node[i].wei]+node[i].val);
49             }
50         }
51         ll ansa=inf;
52         int ansb=0;
53         for(register int i=m; i<=maxm; ++i)
54         {
55             if(f[i]<ansa)
56             {
57                 ansa=f[i];
58                 ansb=i;
59             }
60             else if(f[i]==ansa&&ansb<i)
61             {
62                 ansb=i;
63             }
64         }
65         printf("%lld %d
",ansa,ansb);
66     }
67     return 0;
68 }