记录编号	294336	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]木棍分割	最终得分	100
用户昵称	浮生随想	是否通过	通过
代码语言	C++	运行时间	10.778 s
提交时间	2016-08-11 21:32:13	内存使用	3.36 MiB

/*
主要思想：令 f[i][j] 为前 j 根木棍中切 i 刀，（注意ij位置倒过来是为了方便处理）
并且满足最长长度不超过 Len 的方案数，那么：
状态转移方程： f[i][j]=Σf[i-1][k]((1<=k<=j-1)&&(Sum[j]-Sum[k]<=Len))；
由于k有条件， (Sum[j]-Sum[k]<=Len)所以对于每一个j值，k均对应一个下界。 
优化的时候，用一个sumf记录一下前j-1个的和，然后用一个while循环找出k的下界。
最后用sumf依次减去k处于下界以下的方案数。
*/ 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=100010,mod=10007;
int n,m,ans=0;
ll f[2][maxn],a[maxn],sum[maxn];
bool check(int x){
	int ans=0,cnt=0;
	for(int i=1;i<=n;i++){ 
		cnt+=a[i];
		if(cnt+a[i+1]>x){ 
			cnt=0;
			ans++;
		}
	}
	if(ans>m)return 1;
	else return 0; 
}
int main(){
	freopen("stick.in","r",stdin);
	freopen("stick.out","w",stdout);
	ll l=0,r=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		r+=a[i];
		l=max(l,a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	printf("%lld ",l);//二分答案，不解释了。 
	for(ll i=1;i<=n;i++){
		if(sum[i]<=l){
			f[0][i]=1;
		}
		else break;
	} 
	for(ll i=1;i<=m;i++){
		int pos=i;ll sumf=0;
		int tem=i%2;
		memset(f[tem],0,sizeof f[tem]);
		for(ll j=i+1;j<=n;j++){//j从i+1开始，由于如果要砍i次，至少要i+1段木棍； 
			sumf+=f[!tem][j-1];//在这里，sumf是记录前j-1个的和； 
			while(sum[j]-sum[pos]>l)
				sumf-=f[!tem][pos],pos++;//处理下界，处于下界一下的方案要减去。 
			f[tem][j]=sumf%mod;
			//注意了！！在这里要取模！！sumf在上面不能取模，因为还有一个减的操作；f[tem][j]却必须取模，不然会越界！！ 
		}
		ans+=f[tem][n];ans%=mod;
	}
	printf("%d",ans%mod);
}