• 欢迎光临~

【PNR#2 Div1 D】找零(DP)(贪心)

开发技术 开发技术 2022-10-28 次浏览

找零

题目链接:PNR#2 Div1 D

题目大意

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

思路

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

因为你想要的是就是 (1),那你 ((x+y)bmod 5leqslant xbmod 5+ybmod 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-Bsim x+B) 的结果。
然后复杂度大概是 (O(n+B^2)),那你 (B) 肯定是在能通过的时间内越大越好,这里直接取了 (3000)

然后是别的一些方法口胡一下:
直接设 (f_{i,j}) 为处理好小于等于 (i) 的贡献获得 (j) 的价值需要的最小代价,然后好像是有决策单调性的,可以 (O(nlog 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;
}
程序员灯塔
转载请注明原文链接:【PNR#2 Div1 D】找零(DP)(贪心)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com