BZOJ 1233 乾草堆tower

題意

給定長度為 $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] 的值
}

---