找零

题目链接：PNR#2 Div1 D

题目大意

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

思路

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

因为你想要的是就是 \(1\)，那你 \((x+y)\bmod 5\leqslant x\bmod 5+y\bmod 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({\rm lcm}(1,2,3,4))\)，再枚举 \(1,2,3,4\) 这四种贡献选的值模 \(12,6,4,3\) 的值，强制选调之后再贪心。

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

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#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<y.first/y.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;
}