【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=1044
【题意】
n根木棍拼到一起，最多可以切m刀，问切成后最大段的最小值及其方案数。
【思路】
对于第一问可以二分后贪心判断。
假设第一问得到的答案为L，设f[i][j]前i个木棍切j下且保持段长不超过L的方案数，则有转移式：
f[i][j]=sigma { f[k][j-1] },k<i,suma(k+1,i)<=L
优化：
空间方面可以用个滚动数组。
时间方面由于前缀和sum是递增的，所以我们拿个指针qf维护一个滑动窗口，使得窗口满足suma<=L，tot顺便记一下和就出来了。
【代码】
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
#define rep(a,b,c) for(int a=(b);a>=(c);a--)
using namespace std; typedef long long ll;
const int N = 1e5+;
const int mod = 1e4+; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} int n,m,ans,a[N],sum[N],f[][N],cur,q[N],qf,qr; bool can(int M)
{
int cnt=,tot=;
FOR(i,,n) {
if(tot+a[i]>M) {
if((++cnt)>m) return ;
tot=;
}
tot+=a[i];
}
return ;
} int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
n=read(),m=read();
int L=,R=;
FOR(i,,n)
{
a[i]=read(),
sum[i]=sum[i-]+a[i];
L=max(L,a[i]);
}
R=sum[n];
while(L<R)
{
int M=L+R>>;
if(can(M)) R=M; else L=M+;
}
printf("%d ",L); FOR(j,,m)
{
cur^=;
int tot=,qf=;
FOR(i,,n)
{
if(!j) f[cur][i]=sum[i]<=L;
else {
while(qf<i && sum[i]-sum[qf]>L)
tot=(tot-f[cur^][qf++]+mod)%mod;
f[cur][i]=tot;
}
tot=(tot+f[cur^][i])%mod;
}
ans=(ans+f[cur][n])%mod;
}
printf("%d\n",ans);
return ;
}