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
分析：
注意：最多砍断m个连接处
在统计答案的时候，每一个i都要统计答案
第一问：二分判定
(这次的二分终于是一遍过啦)
第二问：
f[i][j],切割了i下，切到了j,
设s为长度的前缀和
f[i][j]=sigma(f[i-1][k]) (s[j]-s[k]<=len)
时间复杂度O(mn^2)
显然需要优化
优化空间
显然f[i]只与f[i-1]有关，滚动数组
优化时间
若s[j]-s[k]<=ans，
那么s[j-1]-s[k]<=ans（其中j-1>k）
这样我们计算s[j]的时候，把符合要求的k的f值都加到一个g数组中
同时g维护一个后缀和（这就需要j从大到小循环）
在计算j-1的时候，若当前k < j-1，就可以直接把g[k]-g[j]加入j-1
否则k=j-1,暴力维护新的k值
还有一种我yy的做法（还没实现）
看一下(s[j]-s[k]<=len)
因为s[i]是单增的，若s[j]-s[k]<=len,那么k+1也符合，这就是一个区间和
设j的临界转移点是p（s[j]-s[p]<=len,p最小）
当转移j+1的时候
j+1的最佳转移点不可能在p点的左侧，
我们就可以维护一个双端队列，暴力维护下一个状态需要加的区间
tip
m++
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=50005;
const int mod=10007;
const int INF=0x33333333;
int v[N],s[N];
int n,m,mx=0,mn=INF;
int f[3][N],len,p[N];
int q[N],tou,wei,g[N];
void erfen()
{
int l=0,r=s[n],mid;
while (l<r)
{
mid=(l+r)>>1;
int tt=1,d=0;
for (int i=1;i<=n;i++)
{
if (v[i]>mid)
{
tt=INF;
break;
}
if (v[i]+d>mid) tt++,d=v[i];
else d+=v[i];
}
if (tt<=m) r=mid;
else l=mid+1;
}
printf("%d ",l);
len=l;
}
void doit() //f[i][j],切割了i下,切到了j
{
int i,j,k,ans=0;
tou=0,wei=0;
for (i=1;i<=n;i++)
if (s[i]<=len) f[1][i]=1; //切一下长度符合
else break;
int now=0; //滚动数组
for (i=2;i<=m;i++) //切的次数
{
memset(f[now],0,sizeof(f[now]));
memset(g,0,sizeof(g));
k=n+1;
for (j=n;j>1;j--) //s[j]-s[k]<=ans，
//那么s[j-1]-s[k]<=ans 显然j要从大到小
{
if (j>k) f[now][j]+=(g[k]-g[j])%mod;
else k=j;
//暴力维护
while (k>1&&s[j]-s[k-1]<=len)
{
k--;
f[now][j]=(f[now][j]+f[now^1][k])%mod;
g[k]=(g[k+1]+f[now^1][k])%mod;
}
}
ans+=f[now][n]; //最多砍断m个连接处
now^=1;
}
printf("%d",ans);
}
int main()
{
scanf("%d%d",&n,&m); m++; //m++
for (int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
s[i]=s[i-1]+v[i]; //前缀和
}
erfen();
int tt=n;
for (int i=n;i>=1;i--)
{
while (i>=1&&s[i]-s[tt-1]<=len) tt--;
p[i]=tt;
}
doit();
return 0;
}