[HAOI2008]木棍分割

这道题磨了我好久……

第一问可以二分出来，对于每个答案，贪心的分割，最后分割出来的段大于m+1的话就不行，这样的

第二问比较麻烦

有这样一个DP方程：

记前缀和为s

f[i][j]=sigma(f[i-1][k])(s[j]-s[k]<=limit)

f[i][j]表示把前j根木棍分割成i段的方案数

那么，暴力算的话复杂度是O(mn^2)，TLE无疑

我一开始没有注意到题目性质，如果单看DP方程，是想不到什么好的方法的

经pty提醒发现，由于s这个函数是前缀和，因此k的最小值满足单调性，即随着j的递增，k的最小值单调不减

然后记g[i]为f[i]的前缀和函数，即g[i][j]=sigma(f[i][k])(k=1...j)，f的值就等于两个g相减，可以O(1)求

这样对于每一维是线性的，复杂度优化至O(mn)

实际操作时不需要开二维，f也只能开滚动……

第一次提交：MLE，忘记开滚动……

第二次-第n次提交：wa，因为方便取模写了个inc函数，结果顺便把前缀和也取模了……

第n次-第m次提交：wa，贪心分割的过程写wa了……没计算最后一段……

我就是个傻×……不是学clj装B，是真正的那种……

//Lib
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
//Macro
#define rep(i,a,b) for(int i=a,tt=b;i<=tt;++i)
#define drep(i,a,b) for(int i=a,tt=b;i>=tt;--i)
#define erep(i,e,x) for(int i=x;i;i=e[i].next)
#define irep(i,x) for(__typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define read() (strtol(ipos,&ipos,10))
#define sqr(x) ((x)*(x))
#define pb push_back
#define PS system("pause");
typedef long long ll;
typedef pair<int,int> pii;
const int oo=~0U>>1;
const double inf=1e100;
const double eps=1e-6;
string name="",in=".in",out=".out";
//Var
const int mod=10007;
int n,m,ans,maxx;
int s[50008],a[50008];
int f[2][50008],g[50008],p[50008];
inline void inc(int &x,int y){x+=y;x%=mod;}
bool Check(int limit)
{
	int sum=0,cnt=0,i=1;
	rep(i,1,n)
	{
		sum+=a[i];
		if(sum>limit)cnt++,sum=a[i];
	}
	return cnt+1<=m;
}
int Calc()
{
	int l=maxx,r=s[n],mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(Check(mid))r=mid-1;
		else l=mid+1;
	}
	return l;
}
//f[i][j]表示i段j根
int Calc(int limit)
{
	int ret=0,now=0,pre,pos=0;
	f[0][0]=1;g[0]=1;
	rep(i,1,n){while(s[i]-s[pos]>limit)pos++;p[i]=pos;g[i]=1;}
	rep(i,1,m)
	{
		pre=now;now^=1;
		memset(f[now],0,sizeof f[now]);
		rep(j,1,n)
			inc(f[now][j],g[j-1]-g[p[j]]+f[pre][p[j]]);
		inc(ret,f[now][n]);g[0]=0;
		rep(j,1,n){g[j]=g[j-1]+f[now][j];}
	}
	return ret;
}
void Work()
{
	scanf("%d%d",&n,&m);m++;
	rep(i,1,n)scanf("%d",a+i),s[i]=s[i-1]+a[i],maxx=max(maxx,a[i]);
	ans=Calc();
	printf("%d %d\n",ans,Calc(ans));
}
int main()
{
//	freopen((name+in).c_str(),"r",stdin);
//	freopen((name+out).c_str(),"w",stdout);
	Work();
	return 0;
}