小兔的话

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

---

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;
}

---