首页 > 代码库 > bzoj1044题解

bzoj1044题解

2024-09-12 06:41:26   215人阅读

【题意分析】

　　本题等价于如下描述：

　　有一个长度为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 }
View Code

 

bzoj1044题解


联系
我们