BZOJ 1233 干草堆tower

標籤： bzojdp

题意

给定长度为 $n$ 的数组 $a$，要求将这些数分成按顺序分成尽量多组，要求每一组的和都比前一组的和小。

解析

如果正着做的话，你不好确定当组的和应当多大才够，所以可以反转一下序列，反过来考虑，即是，让当前组大于上一组的情况下尽量小。

我们定义 $f(i)$ 表示考虑前 $i$ 个数，末一组和的最小值，$g(i)$ 表示其组数。令 $s(i)$ 表示 $a$ 数组 $[0, i)$ 的和，转移方程便是 $f(i) = \min\limits_{0 \le j < i, f(j) \le s(i) - s(j))}\{s(i) - s(j)\}$。由于 $s(i) - s(j)$ 随着 $j$ 的增加而减小，所以可以倒着枚举 $j$，第一个符合条件的 $j$，便是最优的 $j$ 了。也就是说要找到最大的满足条件的 $j$。

int main()
{
	int n;
	scanf("%d", &n);
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	std::reverse(a.begin(), a.end());
	std::vector<int> s(n + 1);
	for (int i = 0; i < n; i++) {
		s[i + 1] = s[i] + a[i];
	}

	std::vector<int> f(n + 1), g(n + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = i; j > 0;) {
			j--;
			if (f[j] <= s[i] - s[j]) {
				f[i] = s[i] - s[j];
				g[i] = g[j] + 1;
				break;
			}
		}
	}

	printf("%d\n", g[n]);
}

这样的复杂度是 $O(n^2)$ 的，随机数据下表现优异，然而可以这样卡掉：

n = 100000
print(n)
for i in range(n - 1):
    print(1)
print(10000)

考虑优化，这个判断条件是 $f(j) \le s(i) - s(j)$，也就是 $f(j) + s(j) \le s(i)$。令 $h(i) = f(i) + s(i)$，可以把 $h(i)$ 放到值域线段树上做。

你也可以考虑单调队列。所以维护一个单调递增 $j$ 和值 $h(j)$ 都单调递增的单调队列。由于 $s(i)$ 随着 $i$ 的增加而增加，所以在队首如果有 $j_1$，$j_2$，且 $j_1 < j_2$ 都满足条件，前者就不如后者，可以弹出。如果有 $j_1$，$j_2$，且满足 $j_1 < j_2$，$h(j_1) \ge h(j_2)$，那么前者也不如后者，可以弹出。

int main()
{
	int n;
	scanf("%d", &n);
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	std::reverse(a.begin(), a.end());
	std::vector<int> s(n + 1);
	for (int i = 0; i < n; i++) {
		s[i + 1] = s[i] + a[i];
	}

	std::vector<int> f(n + 1), g(n + 1);

	std::deque<int> dq;
	dq.emplace_back(0);
	for (int i = 1; i <= n; i++) {
		while (dq.size() > 1 && f[dq[1]] + s[dq[1]] <= s[i]) {
			dq.pop_front();
		}
		int j = dq.front();
		f[i] = s[i] - s[j];
		g[i] = g[j] + 1;
		while (!dq.empty() && f[dq.back()] + s[dq.back()] >= f[i] + s[i]) {
			dq.pop_back();
		}
		dq.emplace_back(i);
	}

	printf("%d\n", g[n]);
}

附：ChatGPT

system:

You are ChatGPT, a large language model trained by OpenAI. Carefully heed the user’s instructions. Respond using Markdown.

---

user:

解释下面的代码：

#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>

int main()
{
	int n;
	scanf("%d", &n);
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	std::reverse(a.begin(), a.end());
	std::vector<int> s(n + 1);
	for (int i = 0; i < n; i++) {
		s[i + 1] = s[i] + a[i];
	}

	std::vector<int> f(n + 1), g(n + 1);

	std::deque<int> dq;
	dq.emplace_back(0);
	for (int i = 1; i <= n; i++) {
		while (dq.size() > 1 && f[dq[1]] + s[dq[1]] <= s[i]) {
			dq.pop_front();
		}
		int j = dq.front();
		f[i] = s[i] - s[j];
		g[i] = g[j] + 1;
		while (!dq.empty() && f[dq.back()] + s[dq.back()] >= f[i] + s[i]) {
			dq.pop_back();
		}
		dq.emplace_back(i);
	}

	printf("%d\n", g[n]);
}

---

assistant:

这是一段使用单调队列的动态规划程序。以下是代码的一些注释和解释:

#include <algorithm>   // 通用算法库，例如其中的 reverse 函数
#include <cstdio>      // 输入输出流库，例如其中的 printf 和 scanf 函数
#include <queue>       // 包含了 std::deque<> ，双向队列
#include <vector>      // 动态数组容器库

int main() {
    int n;                             // 元素个数
    scanf("%d", &n);                   // 从标准输入读取 n
    std::vector<int> a(n);             // 定义一个容量为 n 的动态数组 a
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);            // 从标准输入读取 n 个整数

    std::reverse(a.begin(), a.end());  // 反转 a 数组

    std::vector<int> s(n + 1);          // 定义一个容量为 n+1 的动态数组 s
    for (int i = 0; i < n; i++)
        s[i + 1] = s[i] + a[i];        // 计算前缀和

    std::vector<int> f(n + 1), g(n + 1);  

    std::deque<int> dq;                
    dq.emplace_back(0);                // 将 0 放入双向队列 dq 中

    for (int i = 1; i <= n; i++) {      // 遍历 i 依次计算 f 和 g 的值
        // 如果 f[dq[1]] + s[dq[1]] <= s[i] 那么将队首元素丢掉
        while (dq.size() > 1 && f[dq[1]] + s[dq[1]] <= s[i]) {
            dq.pop_front();
        }
        int j = dq.front();              

        f[i] = s[i] - s[j];          // 计算 f[i] 的值
        g[i] = g[j] + 1;             // 计算 g[i] 的值 

        // 如果 f[dq.back()] + s[dq.back()] >= f[i] + s[i] 那么将队尾元素丢掉
        while (!dq.empty() && f[dq.back()] + s[dq.back()] >= f[i] + s[i]) {
            dq.pop_back();
        }
        dq.emplace_back(i);          // 将 i 放入队列
    }
    printf("%d\n", g[n]);           // 输出 g[n] 的值
}

---