11.05T1 大步贪心，小步DP

6056 -- 【模拟试题】完全背包

Description

　　Maxtir有一个容量为m的背包。Sao有n种物品，第i种物品的体积为ai，价值为bi。Sao的每种物品都有无限多件，Maxtir可以任取。在不超过背包容量的前提下，Maxtir要求所能获得的最大价值。

Input

　　第1行输入两个正整数n，m。
　　第2至行n+1，每行输入两个正整数ai，bi。

Output

　　输出仅一个整数，表示Maxtir所能获得的最大价值。

Sample Input

【输入样例#1】 2 15 3 2 5 3 【输出样例#1】 10 【输入样例#2】 3 70 71 100 69 1 1 2 140

Sample Output

Hint

【数据范围】
　　对于20%的数据n，m<=10^3。
　　对于40%的数据n，m<=10^4,ai,bi<=10。
　　对于60%的数据n，m<=10^5。
　　对于100%的数据n<=10^6,m<=10^16,ai,bi<=100。

此题我没有开long long爆炸

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<map>
 5 #define N 1000005
 6 using namespace std;
 7 struct node{
 8     long long a,b;
 9 }e[N];
10 long long f[N];
11 bool cmp(const node &a,const node &b){
12     return a.b*1.0/a.a*1.0>b.b*1.0/b.a*1.0;
13 }
14 long long gcd(long long a,long long b){
15     if(a<b)swap(a,b);
16     while(a=a%b)swap(a,b);
17     return b;
18 }
19 map<pair<long long,long long>,long long>check;
20 long long tot;
21 long long read(){
22     long long x=0,f=1;
23     char c=getchar();
24     while(!isdigit(c)){
25         if(c=='-')f=-1;
26         c=getchar();
27     }
28     while(isdigit(c)){
29         x=(x<<3)+(x<<1)+c-'0';
30         c=getchar();
31     }
32     return x*f;
33 }
34 int main(){
35     freopen("backpack.in","r",stdin);
36     freopen("backpack.out","w",stdout);
37     long long n,m;
38     n=read(),m=read();
39     for(long long i=1;i<=n;i++){
40         long long x,y;
41         x=read(),y=read();
42         if(check[make_pair(x,y)])continue;
43         check[make_pair(x,y)]=1;
44         e[++tot].a=x,e[tot].b=y;
45     }
46     n=tot;
47     sort(e+1,e+n+1,cmp);
48     long long max0=0;
49     for(long long i=1;i<=n;i++){
50         for(long long j=i+1;j<=n;j++){
51             max0=max(max0,e[i].a*e[j].a/(e[i].a,e[j].a));
52         }
53     }
54     long long VAL=0;
55     VAL+=(m-max0)/e[1].a*e[1].b;
56     m=max0+(m-max0)%e[1].a;
57     for(long long i=1;i<=n;i++){
58         for(long long j=e[i].a;j<=m;j++){
59             f[j]=max(f[j],f[j-e[i].a]+e[i].b);
60         }
61     }
62     cout<<VAL+f[m];
63     return 0;
64 }

over