传送门 第一问随便二分就过了，此处略去。 第二问DP f[i][j]前i根木棍，砍了j刀的方案数。 转移方程很显然，此处略去。 我们可以滚掉一维。 但是转移要O（n^2m），显然要T 于是我们可以用单调队列+前缀和优化转移，使得时间复杂度降为O（nm) 然后就过了。
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>using namespace std;int f[2][50005],a[50005];int n,m,x,l,r,mi,s,sum,c,k,ans;int main(){ scanf("%d%d",&n,&m); m++; for (int i=1;i<=n;i++){ scanf("%d",&x); a[i]=a[i-1]+x; if (x>l) l=x; } r=a[n]; while (l<r){ mi=(l+r)/2; s=1; sum=1; for (int i=1;i<=n;i++) if (a[i]-a[s-1]>mi){ sum++; s=i; } if (sum>m) l=mi+1; else r=mi; } PRintf("%d ",l); c=ans=0; f[0][0]=1; for (int i=1;i<=m;i++){ c=1-c; k=sum=0; for (int j=0;j<=n;j++){ while (a[j]-a[k]>l){ sum=(sum-f[1-c][k]+10007)%10007; k++; } f[c][j]=sum; sum=(sum+f[1-c][j])%10007; } ans=(ans+f[c][n])%10007; } printf("%d",ans); return 0;}新闻热点
疑难解答
