Description
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连 接处,
砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长 度最大的一段长度最小. 并将结果mod
10007。。。
Input
输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.
Output
输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.
Sample Input
3 2
1
1
10
Sample Output
10 2
HINT
两种砍的方法: (1)(1)(10)和(1 1)(10)
题解
第一问二分答案On判定很水吧。。
第二问设一个dp
f[i][j]表示1~i，切了j刀的方案数
方程就是f[i][j]=sigma(f[k][j-1])，满足k+1~i这一段＜=第一问的答案
考虑优化
空间上很明显可以看出，f[i][j]只会与f[k][j-1]有关，所以可以滚动一下
时间上，用一个前缀和优化一下，单调队列的思想用一下可以做到nm吧
具体可以看代码可读性很高吧
前缀和千万不要取模。。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod=10007;
int n,m;
int a[51000];
bool check(int p)
{int tmp=0,len=0;for(int i=1;i<=n;i++){len+=a[i];if(len>p)tmp++,len=a[i];}if(len>p)return false;if(tmp>m)return false;return true;
}
int f[2][51000];//1~j成一段了
int sum[51000],fro[51000];
int main()
{scanf("%d%d",&n,&m);int s=0;for(int i=1;i<=n;i++){
scanf("%d",&a[i]);s+=a[i];fro[i]=fro[i-1]+a[i];}int l=1,r=s,ans;while(l<=r){int mid=(l+r)/2;if(check(mid)){ans=mid;r=mid-1;}else l=mid+1;}printf("%d ",ans);int st=0,ret=0;s=0;for(int i=1;i<=n;i++){s+=a[i];if(s<=ans)f[st][i]=1;else break;}sum[0]=0;for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+f[st][i])%mod;for(int i=1;i<=m;i++){st^=1;memset(f[st],0,sizeof(f[st]));int u=0;for(int j=1;j<=n;j++){while(fro[j]-fro[u]>ans)u++;if(u!=0)f[st][j]=(f[st][j]+sum[j-1]-sum[u-1])%mod;else f[st][j]=(f[st][j]+sum[j-1])%mod;}/*for(int j=1;j<=n;j++){int sum=a[j];for(int k=j-1;k>=0;k--){if(sum>ans)break;f[st][j]=(f[st][j]+f[st^1][k])%mod;sum+=a[k];}}*/sum[0]=0;for(int j=1;j<=n;j++)sum[j]=(sum[j-1]+f[st][j]);ret=(ret+f[st][n])%mod;}printf("%d\n",ret);return 0;
}