BZOJ 1233 干草堆tower

标签: bzojdp

题意

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

解析

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

我们定义 表示考虑前 个数,末一组和的最小值, 表示其组数。令 表示 数组 的和,转移方程便是 。由于 随着 的增加而减小,所以可以倒着枚举 ,第一个符合条件的 ,便是最优的 了。也就是说要找到最大的满足条件的

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

这样的复杂度是 的,随机数据下表现优异,然而可以这样卡掉:

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

考虑优化,这个判断条件是 ,也就是 。令 ,可以把 放到值域线段树上做。

你也可以考虑单调队列。所以维护一个单调递增 和值 都单调递增的单调队列。由于 随着 的增加而增加,所以在队首如果有 ,且 都满足条件,前者就不如后者,可以弹出。如果有 ,且满足 ,那么前者也不如后者,可以弹出。

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] 的值
}