首页 > 代码库 > bzoj1044题解
bzoj1044题解
【题意分析】
本题等价于如下描述:
有一个长度为n的正整数序列,要求将其分解成m+1个子串,使最大子串和最小。求这个最大子串和及对应的分解方案数。
【解题思路】
第一问二分+贪心即可。容易证明对于确定的最大子串和,分解子串使子串个数最小是一个具有最优子结构的问题。复杂度O(nlog2Σli)。
第二问DP即可。先预处理前缀和Si=∑lj(j∈[1,i])。
然后考虑状态:f[i][j]表示前i个元素分解成j个子串的合法方案数。
易得转移方程:f[i][j]=Σf[k][j-1](k∈[j-1,i)且Si-Sk≤ans)
但直接DP会TLE(时间复杂度O(mn2))+MLE(空间复杂度O(mn)),于是考虑优化:
•空间复杂度:因为DP向量f[][j]只跟f[][j-1]有关,可以用滚动数组优化,空间复杂度O(n);
•时间复杂度:固定j时,随着i的递增,可行的最小k是单调不减的,所以可以用单调队列优化,时间复杂度O(mn);
最后答案即为∑f[n][j](j∈[1,m+1])。总复杂度O(n(m+log2Σli))。
【参考程序】
1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 5 #define __debug 6 #ifdef __debug 7 #define Function(type) type 8 #define Procedure void 9 #else10 #define Function(type) __attribute__((optimize("-O2"))) inline type11 #define Procedure __attribute__((optimize("-O2"))) inline void12 #endif13 14 using namespace std;15 16 static const int AwD=10007;17 Function(int&) inc(int&x,const int&y)18 {19 return (x+=y)>=AwD?x-=AwD:x;20 }21 Function(int&) dec(int&x,const int&y)22 {23 return (x-=y)< 0 ?x+=AwD:x;24 }25 26 static int n,m;27 int L[50005],S[50005]={0},las[50005],f[50005];28 29 int main()30 {31 scanf("%d%d",&n,&m); int l=0,r=0;32 range(i,1,n+1) scanf("%d",L+i),l=max(l,L[i]),r+=L[i];33 while(l<r)34 {35 int mid=l+r>>1,cnt=0,sum=0;36 range(i,1,n+1) if((sum+=L[i])>mid) sum=L[i],++cnt;37 cnt>m?l=mid+1:r=mid;38 }39 printf("%d ",r);40 range(i,1,n+1) if((S[i]=S[i-1]+L[i])<=r) las[i]=1;41 int ans=las[n];42 range(i,2,m+2)43 {44 int h=1,sum=0; range(j,1,i) sum+=las[j],f[j]=0;45 range(j,i,n+1)46 {47 for(;S[j]-S[h]>r;dec(sum,las[h++]));48 f[j]=sum,inc(sum,las[j]);49 }50 memcpy(las,f,sizeof las),inc(ans,f[n]);51 }52 return printf("%d\n",ans),0;53 }
bzoj1044题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。