题目描述

给

n

个木棍，最多分成

m+1

段，输出连续长度和的最大值的最小值，并计算出方案数。

Q1：二分+贪心

考虑枚举的长度中包含尽可能多的木棍，如果枚举的长度符合要求，那么将右边界修改为枚举的长度

mid

;否则将左边界修改为

mid+1

。

主要代码如下：

CPP

while(r>l)
	{
		int mid=(r+l)>>1,sum=0,tot=0;
		for(int i=1;i<=n;i++)
		{
			sum+=a[i];
			if(sum==mid){++tot,sum=0;continue;}
			if(sum+a[i+1]>mid) ++tot,sum=0;
		}
		if(sum) ++tot;
		if(tot>m+1) l=mid+1;
		else r=mid;
	}

Q2：前缀和优化DP+滚动数组

用

b

数组记录前缀和，用

f[i][j]

表示将前

i

段木棍切

j

次的最大方案数（切

j

次是分成了 $j+1$ 段），在区间和小于

l

的情况下枚举

k

,于是得到转移方程：

f[i][j] = \sum \limits_{k=0}^{i-1} f[k][j]

k

满足

b[i]-b[k]≤l

显然，上面

O(mn^2)

的复杂度是不能接受的，盯着我们的DP转移方程我们发现，由于区间和的线性，我们的

k

有一个最小值，使后面的

k

都成立，所以可以对其进行预处理，代码如下：

CPP

for(int i=1;i<=n;i++)
		while(j<n&&b[j+1]-b[i]<=l) pre[++j]=i;

打到现在，我们发现了一个问题,

f[50000][1000]

无法实现。于是再次回到 DP 方程，经过一个半小时的瞪眼后，我们又发现

f[i]

只受

f[i-1]

的影响，所以很自然的想到使用滚动数组，于是我们得到了以下代码：

CPP

	for(int i=1;i<=n;i++)
		g[i]=g[i-1]+(b[i]<=l);
    for(int j=1;j<=m;j++)
	{
		for(int i=2;i<=n;i++) f[i]=g[i-1]-g[pre[i]-1];
		for(int i=1;i<=n;i++) g[i]=(g[i-1]+f[i])%mod;
		ans=(ans+f[n])%mod;
	}

正当我们兴高采烈地等着 AC 时，去发现 WA 了两个点，于是又开始瞪眼，最后瞪了半个小时（其实是旁边的神犇看出来的），我们的

f[i]

是做的减法，如果前者取模后小于后者，则会出现负数，所以应该输出(ans%mod+mod)%mod,最后愉快 AC (〃'▽'〃)

CPP

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+5,mod=1e4+7;
int a[N],b[N],f[N],g[N],pre[N];
int read()
{
	int x=0,a=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())
		if(c=='-') a=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=x*10+c-'0';
	return x*a;
}
void write(int x)
{
	if(x<0)x*=-1,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return;
}
signed main()
{
	int n,m,r,l=0,j=0,ans=0;
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		b[i]=b[i-1]+a[i];
		l=max(l,a[i]);
	}
	r=b[n];
	while(r>l)
	{
		int mid=(r+l)>>1,sum=0,tot=0;
		for(int i=1;i<=n;i++)
		{
			sum+=a[i];
			if(sum==mid){++tot,sum=0;continue;}
			if(sum+a[i+1]>mid) ++tot,sum=0;
		}
		if(sum) ++tot;
		if(tot>m+1) l=mid+1;
		else r=mid;
	}
	for(int i=1;i<=n;i++)
		g[i]=g[i-1]+(b[i]<=l);
	for(int i=1;i<=n;i++)
		while(j<n&&b[j+1]-b[i]<=l) pre[++j]=i;
	for(int j=1;j<=m;j++)
	{
		for(int i=2;i<=n;i++) f[i]=g[i-1]-g[pre[i]-1];
		for(int i=1;i<=n;i++) g[i]=(g[i-1]+f[i])%mod;
		ans=(ans+f[n])%mod;
	}
	write(l),putchar(' '),write((ans%mod+mod)%mod);
	return 0;
}

题解：P2511 [HAOI2008] 木棍分割

文章操作