【集训DAY13】Backpack【动态规划】【贪心】

思路：

我们先贪心，把m压缩，然后剩下的空位再DP。
正确性不知道。

这里的是一种水法，由于数据太水得了满分，大家勿扣

$code$

#include<iostream>
#include<cstdio>
#include<algorithm>
#define re register
#define ll long long

using namespace std;

const ll MAXN = 1e6 + 10;

ll n, tot, k, f[MAXN];
ll m;
struct node {
    
	ll wei, val;
}a[MAXN], b[MAXN];

inline bool cmp1(re node x, re node y) {
    
	if(x.wei != y.wei) return x.wei < y.wei;
	else return x.val > y.val;
}

inline bool cmp2(re node x, re node y) {
    
	if(x.val != y.val) return x.val < y.val;
	else return x.wei < y.wei;
}

inline bool cmp3(re node x, re node y) {
    
	if(m / x.wei * x.val != m / y.wei * y.val)
		return m / x.wei * x.val > m / y.wei * y.val;
	else return x.wei < y.wei;
}

int main() {
    
	freopen("backpack.in", "r", stdin);
	freopen("backpack.out", "w", stdout);
	scanf("%lld%lld", &n, &m);
	for(re ll i = 1; i <= n; ++ i) scanf("%d%d", &a[i].wei, &a[i].val);
	sort(a + 1, a + 1 + n, cmp1);
	for(re ll i = 1; i <= n; ) {
    
		re ll j = i + 1;
		while(a[j].wei == a[i].wei && j <= n) j ++;
		-- j;
		b[++ tot].wei = a[i].wei, b[tot].val = a[i].val;
		i = j + 1;
	}
	n = tot;
	tot = 0;
	sort(b + 1, b + 1 + n, cmp2);
	for(re ll i = 1; i <= n; ) {
    
		re ll j = i + 1;
		while(b[j].val == b[i].val && j <= n) j ++;
		-- j;
		a[++ tot].wei = b[i].wei, a[tot].val = b[i].val;
		i = j + 1;
	}
	n = tot;
	if(m * n <= 100000000 && m <= 1000000) {
    
		for(re ll i = 1; i <= n; i ++)
			for(re ll j = a[i].wei; j <= m; j ++)
				f[j] = max(f[j], f[j - a[i].wei] + a[i].val);
		printf("%d", f[m]);
	}
	else {
    
		sort(a + 1, a + 1 + n, cmp3);
		re ll ans = 0;
		for(re ll i = 1; i <= n; i ++) {
    
			ans = ans + m / a[i].wei * a[i].val;
			m -= m / a[i].wei * a[i].wei;
		}
		printf("%lld", ans);
	}
	return 0;
}