第一个问题直接二分答案
然后第二个问题直接在二分出的答案下跑一遍 $dp$，设 $f[i][j]$ 表示当前已经切了 $i$ 次考虑完前 $j$ 个位置并且强制切 $j,j+1$ 时的方案数
那么有转移 $f[i][j]=\sum_{k=L}^{j-1}f[i-1][k]$，发现随着 $j$ 增加 $L$ 不减，所以转移可以用前缀和并动态维护左端点优化到 $O(1)$
初始状态特殊处理一下就行，然后因为有强制切，发现切 $n,n+1$ 是没意义的，所以 $ans=\sum_{i=1}^{m+1}f[i][n]$，$m+1$ 是因为最后切的一次没意义
然后滚动数组把 $i$ 滚动掉即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=5e4+7,mo=10007; inline int fk(int x) { return x>=mo ? x-mo : x; } int n,m,a[N],sum[N],f[N],sf[N]; int mx,Ans; bool check(int p) { int now=0,cnt=0; for(int i=1;i<=n;i++) { if(now+a[i]>p) now=0,cnt++; now+=a[i]; if(now>p||cnt>m) return 0; } return 1; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i]; int L=1,R=sum[n]; while(L<=R) { int mid=L+R>>1; if(check(mid)) mx=mid,R=mid-1; else L=mid+1; } for(int i=1;i<=n;i++) { if(sum[i]<=mx) f[i]=1; sf[i]=fk(sf[i-1]+f[i]); } Ans+=f[n]; for(int i=1;i<=m;i++) { int p=0; for(int j=1;j<=n;j++) { while(sum[j]-sum[p]>mx) p++; f[j]=fk( sf[j-1]-(p ? sf[p-1] : 0) +mo ); } sf[0]=0; for(int j=1;j<=n;j++) sf[j]=fk(sf[j-1]+f[j]); Ans=fk(Ans+f[n]); } printf("%d %d\n",mx,Ans); }
原文：https://www.cnblogs.com/LLTYYC/p/11438713.html