博客

1.

题目链接

。首先第一问，由于木棍的长度都是非负数，所以前缀和单调不减，这样直接二分这个maxLen就可以得到答案。然后第二问，设dp[i][j]表示把对于前i个，切了j刀满足要求的方案数。这样，dp[i][j]的转移其实很好推：

然后，这里开始优化：

(1)首先是空间优化，可以看到，j之和j-1有关，那么滚动一下空间O(n).

(2).时间优化，虽然dp方程的k每次都是从1开始枚举的，但是实际上这显然是存在多余，因为sum是单调不减的，所以对于当前的i一定存在一个最左边的边界，我们可以记录这个边界，然后记录这个边界到当前位置上一步的值，这样我们每次询问只需要把最左边的边界的向右推移，然后减去那些过期的值即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int mod = 10007;
int n, m, MaxLen, Ans, Sumf;
int A[N], Sum[N], f[N][2];
bool check(int x)
{
	if (x < MaxLen)return false;
	int cur = 0, cut = 0;
	for (int i = 1; i <= n; i++)
	{
		if (cur + A[i] > x)
		{
			cut++;
			cur = 0;
		}
		if (cut > m)return false;
		cur += A[i];
	}
	return true;
}
int main()
{
	while (~scanf("%d%d", &n, &m))
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &A[i]);
			Sum[i] = Sum[i - 1] + A[i];
			MaxLen = max(MaxLen, A[i]);
		}
		int l = 0, r = 1e6;
		while (l <= r)
		{
			int mid = l + r >> 1;
			if (check(mid))r = mid - 1;
			else l = mid + 1;
		}
		int len = r + 1;
		memset(f, 0, sizeof(f));
		Ans = 0;
		int Now = 0, Last = 1, Mink;
		for (int i = 0; i <= m; i++)
		{
			Sumf = 0;
			Mink = 1;
			for (int j(1); j <= n; j++)
			{
				if (i == 0)
				{
					if (Sum[j] <= len)f[j][Now] = 1;
					else f[j][Now] = 0;
				}
				else
				{
					while (Mink<j && Sum[j] - Sum[Mink]>len)
					{
						Sumf -= f[Mink][Last];
						Sumf = (Sumf + mod) % mod;
						Mink++;
					}
					f[j][Now] = Sumf;
				}
				Sumf += f[j][Last];
				Sumf %= mod;
			}
			Ans += f[n][Now];
			Ans %= mod;
			Now ^= 1;
			Last = Now ^ 1;
		}
		printf("%d %d\n", len, Ans);
	}
}