【BZOJ1044】[HAOI2008]木棍分割

题面

bzoj

洛谷

题解

第一问显然可以二分出来的。

第二问：

设\(dp[i][j]\)表示前\(i\)个，切了\(j\)组的方案数

发现每次转移都是从前面一个区间过来的

直接前缀和优化就好了

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

	register int data = 0, w = 1;

	register char ch = 0;

	while (!isdigit(ch) && ch != '-') ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

	return w * data;

}

const int Mod = 10007;

void pls(int &x, int y) { x += y; if (x >= Mod) x -= Mod; }

void dec(int &x, int y) { x -= y; if (x < 0) x += Mod; }

const int MAX_N = 50005;

int N, M, ans1, ans2, len[MAX_N], L[MAX_N], prv[MAX_N];

bool check(int v) {

	int cnt = 0, s = 0;

	for (int i = 1; i <= N; i++) {

		if (s + len[i] > v) ++cnt, s = len[i];

		else s += len[i];

		if (cnt > M) return 0;

	}

	return 1;

}

int solve() {

	int l = *max_element(&len[1], &len[N + 1]), r = L[N], res = L[N];

	while (l <= r) {

		int mid = (l + r) >> 1;

		if (check(mid)) r = mid - 1, res = mid;

		else l = mid + 1;

	}

	return res;

}

int sum1[MAX_N], sum2[MAX_N];

int main () {

	N = gi(), M = gi();

	for (int i = 1; i <= N; i++) L[i] = L[i - 1] + (len[i] = gi());

	ans1 = solve();

	for (int i = 1; i <= N; i++) {

		int l = 1, r = i; prv[i] = i;

		while (l <= r) {

			int mid = (l + r) >> 1;

			if (L[i] - L[mid - 2] <= ans1) prv[i] = mid, r = mid - 1;

			else l = mid + 1;

		}

	}

	for (int i = 1, j = 1; i <= N; i++) {

		while (L[i] - L[j - 1] > ans1 && j < i) ++j;

		if (L[i] - L[j - 1] <= ans1) prv[i] = max(j - 2, 0);

	}

	for (int i = 1; i <= N; i++) sum1[i] = sum1[i - 1], pls(sum1[i], (L[i] <= ans1));

	for (int i = 1; i <= M; i++) {

		for (int j = 1; j <= N; j++) sum2[j] = sum1[j - 1], dec(sum2[j], sum1[prv[j]]);

		for (int j = 1; j <= N; j++) sum1[j] = sum1[j - 1], pls(sum1[j], sum2[j]);

		pls(ans2, sum2[N]);

	}

	printf("%d %d\n", ans1, ans2);

	return 0;

}