【PNR#2 Div1 D】找零（DP）（贪心）

找零

题目链接：PNR#2 Div1 D

题目大意

有 500,100,50,10,5,1 这些面额的纸币，你有 X 块钱，使用最少的纸币数表示的。
然后有一些物品，每种只有一个，有费用。
每次你可以选择一些没买过的买，付一定的钱，然后会找你钱，用最小的纸币数。
然后要你最大化最后 1 元纸币的数量。

思路

首先你肯定不会自己交 $1$ 元的，显然不会变回来更多的。
然后我们还有一个事情就是我们只会一个一个的买。

因为你想要的是就是 $1$，那你 $(x+y)\mathrm{mod}5⩽x\mathrm{mod}5+y\mathrm{mod}5$ 这是显然的。

然后你会发现你 $500,100,50,10$ 其实都不重要，我们都可以把它当做是 $5$。
也就是我们只需要当做只有 $5,1$。
那就相当于每个物品有自己的费用和贡献，要你 DP 使得贡献和最大。

自此已经可以得到 $O(n^2)$ 的背包做法。
考虑优化，发现区别于普通背包的点是贡献只有 $0,1,2,3,4$ 五种。
（你说 $1,2,3,4$ 四种也行）

这里其实有很多方法，先说我写的这个：
你考虑贪心，那就是我们肯定要让每个贡献需要的费用最小。
那考虑按这个排序然后选，但是显然需要调整。

不过同一个贡献的我们肯定是按费用从小到大选这个肯定没错。
那我们要改变的就是这个贡献选的数量。
那你设置一个波动 $B$，那如果贪心选的数量是 $x$，那我们就只需要 DP $x-B\sim x+B$ 的结果。
然后复杂度大概是 $O(n+B^2)$，那你 $B$ 肯定是在能通过的时间内越大越好，这里直接取了 $3000$。

然后是别的一些方法口胡一下：
直接设 $f_{i,j}$ 为处理好小于等于 $i$ 的贡献获得 $j$ 的价值需要的最小代价，然后好像是有决策单调性的，可以 $O(n\log n)$ 转移一步。
也可以类似于上面的贪心，把每种贡献打包成 $12(\mathrm{lcm}(1,2,3,4))$，再枚举 $1,2,3,4$ 这四种贡献选的值模 $12,6,4,3$ 的值，强制选调之后再贪心。

还可以把 $1,3$ 分一组，$2,4$ 分一组（反正分成两组），算出算出内部选的优情况，然后再双指针类似扫两组的组合。

代码

#include
#include
#include
#include
#define ll long long

using namespace std;

const ll N = 1e5 + 100;
const ll B = 3000;
ll n, X, f[N * 5];
pair <ll, ll> g[N];
vector <ll> A[5];
ll may[5];

//x.first/x.second
bool cmp(pair <ll, ll> x, pair <ll, ll> y) {
	return x.first * y.second < y.first * x.second;
}

int main() {
	scanf("%lld %lld", &n, &X);
	for (ll i = 1; i <= n; i++) {
		ll a; scanf("%lld", &a);
		ll x = (a + 4) / 5; ll y = x * 5 - a;
		g[i] = make_pair(x, y);
		A[y].push_back(x);
	}
	for (ll i = 0; i < 5; i++) sort(A[i].begin(), A[i].end());
	
	sort(g + 1, g + n + 1, cmp);
	ll num = X / 5;
	for (ll i = 1; i <= n; i++) {
		if (num < g[i].first) break;
		num -= g[i].first; may[g[i].second]++;
	}
	num = X / 5; ll an = X % 5, sum = 0;
	memset(f, 0x7f, sizeof(f)); f[0] = 0;
	for (ll sz = 0; sz < 5; sz++) {
		ll l = max(1ll, may[sz] - B), r = min((ll)A[sz].size(), may[sz] + B);
		for (ll i = 1; i < l; i++) {
			an += sz; num -= A[sz][i - 1];
		}
		for (ll i = l; i <= r; i++) {
			for (ll j = sum; j >= 0; j--) {
				f[j + sz] = min(f[j + sz], f[j] + A[sz][i - 1]);
			}
			sum += sz;
		}
	}
	
	for (ll i = sum; i >= 0; i--)
		if (f[i] <= num) {
			an += i; break;
		}
	printf("%lld", an);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59