夏晓光(loveJY)的博客

nmd细节

设$f_{i,j}$表示前i个棍分成j组的方案数

转移式子很简单f_{i,j}=\sum_{k<i,sum[i]-sum[k]<=Max}f_{k,j-1}

然后j这维可以滚动,同时可以前缀和优化...

不过这个有个你妈的细节,就是$f_{i,j}=sum_{i-1,j-1}-sum_{tp-1,j-1}$

因为$f_{i,j-1}$这个是不能转移到$f_{i,j}$的....毕竟没有空组!!

唉...但是只WA了一个点,让人麻木

写的时候多想了好多强加了好多限制使得看上去繁琐了....

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e4 + 7;
const int MAXN = 1e5 + 7;
int n, m, S;
int a[MAXN], pre[MAXN];
int Max, MM;

inline int chk(int x) {
	int tmp = 0;
	int ccnt = 0;
	for(int i = 1; i <= n; ++i) {
		if(tmp + a[i] > x) {
			ccnt++;
			tmp = a[i];
		} else tmp += a[i];
	}
	return (m >= ccnt);
}

inline void solve1() {
	int l = MM, r = S, mid;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(chk(mid)) {
			r = mid - 1;
			Max = mid;
		} else l = mid + 1;
	}
}

ll f[2][MAXN], sum[2][MAXN], ans;
inline void solve2() {
	int tp = 0;
	int t = 0;
	for(int i = 1; i <= n; ++i) {
		if(pre[i] <= Max)
			f[1][i] = 1;
		sum[1][i] = sum[1][i - 1] + f[1][i];
	}
	for(int j = 2; j <= m + 1; ++j) {
		tp = 0;
		// puts("qwq");
		for(int i = j; i <= n; ++i) {
			while(tp <= i && pre[i] - pre[tp] > Max)++tp;
			sum[t][i] = sum[t][i - 1];
			// printf("%d %din->%lld %lld\n", i, tp, sum[t ^ 1][i], sum[t ^ 1][tp - 1]);
			if(tp != 0)
				f[t][i] = sum[t ^ 1][i - 1] - sum[t ^ 1][tp - 1];
			else
				f[t][i] = sum[t ^ 1][i - 1];
			// printf("%lld??\n", f[t][i]);
			f[t][i] = (f[t][i] + P) % P;
			sum[t][i] = (sum[t][i] + f[t][i]) % P;
		}
		ans = (ans + f[t][n]) % P;
		t ^= 1;
		for(int i = 0; i <= n; ++i)
			f[t][i] = sum[t][i] = 0;
	}
	printf("%lld\n", ans);
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pre[i] = pre[i - 1] + a[i];
		S += a[i];
		MM = max(MM, a[i]);
	}
	solve1();//解决第一问
	printf("%d ", Max);
	solve2();//缀和优化第二维
	return 0;
}