2021.12.06 P2511 [HAOI2008]木棍分割(动态规划)

2021.12.06 P2511 [HAOI2008]木棍分割(动态规划)

https://www.luogu.com.cn/problem/P2511

题意：

有n根木棍, 第i根木棍的长度为 \(L_i\) ,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。

分析：

对于第一问，首先二分答案找出ans。

对于第二问，设 sum[i] 表示前 \(i\) 个木棍的长度之和，对于每个木棍 \(i\) ，可以找出在它最前面的木棍 \(j\) ，满足 \(sum_i-sum_j<=ans\) ，把结果存在数组 pos 中。对于前 \(j\) 根木棍分成 \(i\) 组，那么

\[f[i][j]=\sum_{k=pos_j}^{j-1}f[i-1][k]\\
fin=\sum_{i=1}^{m+1}f[i][n]
\]

一看就懂，时间复杂度为傲人的 \(O(n^3)\) ，你可以试试，反正我挂了 。

忽然发现

\[设g[i][j]=\sum_{k=1}^{j}f[i][k]\\
f[i][j]=g[i-1][j]-g[i-1][pos[j]-1]
\]

时间复杂度依旧傲人，不过好了很多，成为 \(O(n^2)\) 。不过你确定不想想空间吗？2个 \(1e7\) 的数组也不小啊。

继续优化：实际上 f 与 g 只和上一轮有关，滚动成一维数组就成~

代码如下：

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=5e4+10;

const int mod=1e4+7;

int n,m,sum[N],pos[N],a[N],f[N],g[N];

inline int check(int maxn){

	int tot=0,len=0;

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

		if(len+a[i]>maxn)++tot,len=a[i];

		else len+=a[i];

		if(tot>m)return 0;

	}

	return tot<=m;

}

int main(){

	IOS;

	cin>>n>>m;

	int L=0,R=0,ans;

	for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i],L=max(L,a[i]);

	R=sum[n];

	while(L<R){

		int mid=(L+R)>>1;

		if(check(mid))ans=mid,R=mid;

		else L=mid+1;

	}

	cout<<ans<<" ";

	int lasti=0;

	for(int i=1;i<=n;i++)

	for(;lasti<i;lasti++)if(sum[i]-sum[lasti]<=ans){

		pos[i]=lasti;

		break;

	}

	int fin=sum[n]<=ans;

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

		if(sum[i]<=ans)f[i]=1;

		g[i]=(g[i-1]+f[i])%mod;

	}

	for(int i=2;i<=m+1;i++){

		for(int j=1;j<=n;j++){

			f[j]=g[j-1];

			if(pos[j]>=1)f[j]=((f[j]-g[pos[j]-1])%mod+mod)%mod;

		}

		for(int j=1;j<=n;j++)g[j]=(g[j-1]+f[j])%mod;

		fin=(fin+f[n])%mod;

	}

	cout<<fin;

	return 0;

}

2021.12.06 P2511 [HAOI2008]木棍分割(动态规划)的相关教程结束。