小兔的话

欢迎大家在评论区留言哦~


CF10E Greedy Change

题目限制

  • 时间限制:2.00s
  • 内存限制:250.00MB
  • 标准输入
  • 标准输出

题目知识点

  • 思维

题目来源

「 CodeForces」10E Greedy Change


为了方便大家阅读通畅,题目可能略有改动,保证不会造成影响

题目

题目翻译

给定 \(n\) 种货币,每种货币数量无限
现在要求以最少的货币数目表示一个正整数 \(S\)
一种方法是 DP 求一个最优解了;另一种方法是贪心:每次取当前能取的最大货币
现在你的任务是贪心是不一定最优的:找到最小的 \(S\),使得 贪心求出的最优解DP求出的最优解 差,或说明这样的 \(S\) 不存在

格式

输入格式

输入共 \(2\) 行:
\(1\) 行:包含一个整数 \(n\)
\(2\) 行:包含 \(n\) 个整数 \(a_i\),表示每个硬币面值

输出格式

如果不存在 \(S\) 使得 贪心求出的最优解DP求出的最优解 差,则输出 -1 ;否则输出最小的 \(S\)

样例

样例 \(1\)

样例输入

5
25 10 5 2 1

样例输出

-1

样例解释

不存在 \(S\) 使得 贪心求出的最优解DP求出的最优解

样例 \(2\)

样例输入

3
4 3 1

样例输出

6

样例解释

\(S = 6\) 时,贪心做法求出的最优解为 \(3 \ (4 + 1 + 1)\),DP做法求出的最优解为 \(2 \ (3 + 3)\)

提示

数据范围

对于 \(100\%\) 的数据:满足 \(1 \leq n \leq 400\)\(1 \leq a_i(1 \leq i \leq n) \leq 10^9\),且保证 \(a\) 数组严格降序排列且 \(a_n = 1\)


思路

首先肯定不可能枚举 \(S\),因为题目没有告诉我们 \(S\) 的上界,暴力枚举肯定会 \(TLE\)
根据数据范围 \(1 \leq n \leq 400\)\(1 \leq a_i(1 \leq i \leq n) \leq 10^9\),可以看出应该是一个 \(O(n ^ 3)\) 或者 \(O(n ^ 2 \ \mathrm{log} \ a_i)\) 的算法
不知道怎么产生的 \(\mathrm{log} \ a_i\),所以考虑 \(O(n ^ 3)\) 的算法

那么对于一个数值 \(S\),什么情况下 DP 比 贪心 更优呢?
假设 \(S\) 能在 \(a_{k \in [i + 1, j]}\) 中取完后没有剩余(最少取了 \(p\) 次),而贪心取完了 \(a_i\) 后只能取 \(a_{k \in[j + 1, n]}\) 了(包括取 \(a_{k \in[j + 1, n]}\) 一共取了 \(q\) 次);若 \(p < q\),则贪心不是最优的
因此我们可以枚举区间 \([i, j]\),如果满足 \(p < q\),则找到了一个解 \(S\);最后在所有的 \(S\) 中取最小的即可


分析

知道了大概思路,如何求 \(p\)\(q\) 呢?

我们要保证 \(S\) 能在 \(a_{k \in [i + 1, j]}\) 中取完 并且 贪心取完了 \(a_i\) 后只能取 \(a_{k \in[j + 1, n]}\)

  • 先保证前者:先选一个数 \(A\),记 \(A\)\(a_{k \in [i + 1, j]}\) 中取完之后剩下 \(B\),那么 \(S\) 就可以是 \(A - B\)\(A\) 如何选就要看后者了)
  • 再保证后者:因为 \(B\) 是取完后剩下的,所以 \(B < a_j\);要保证 \(S > a_i\)\(S \ \mathrm{mod} \ a_i < a_j\),不妨假设 \(S\) 只取了 \(1\)\(a_i\)(因为要保证当前 \(S\) 也最小嘛),所以 \(S > a_i\)\(S - a_i < a_j\);因为 \(B < a_j\),则 \(a_j - B \geq 1\);因此可以选一个 \(A < a_i\),使得 \(A + a_j - B \geq a_i\),能保证这 \(2\) 个式子的只有 \(A = a_i - 1\) 了;得到 \(A\) 后,\(B\)\(S\) 也就出来了

对每个区间 \([i, j]\),按照上面的方法计算 \(p, q\) 就可以了
如果所有区间都不存在 \(p < q\) 就输出 \(-1\)


\(\mathrm{code}\)

#include <cstdio>

int Max(int a, int b) { return (a > b) ? a : b; }
int Min(int a, int b) { return (a < b) ? a : b; }

int rint()
{
	int x = 0, fx = 1; char c = getchar();
	while (c < '0' || c > '9') { fx ^= (c == '-' ? 1 : 0); c = getchar(); }
	while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	if (!fx) return -x;
	return x;
}

const int MAX_n = 400;

int n, res = 2e9;
int v[MAX_n + 5];

int main()
{
	n = rint();
	for (int i = 1; i <= n; i++)
		v[i] = rint();
	bool ok = false;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			int dp = 0, count = 0, now = v[i] - 1; // A = v[i] - 1
			for (int k = i + 1; k <= j; k++)
				dp += now / v[k], now %= v[k]; // 求出 B
			int temp = now = v[i] - 1 - now + v[j]; // 计算出 S, 备份一下
			for (int k = 1; k <= n; k++)
				count += now / v[k], now %= v[k];
			if (dp + 1 < count) res = Min(res, temp), ok = true;
			// dp + 1 是因为之前多加了一个 v[j]
			// 若 p < q, 则 当前S 可能是答案
		}
	}
	printf("%d\n", ok ? res : -1);
	return 0;
}


05-15 12:56