给出一个长度为n的正整数序列,要求把它划分成若干个连续的区间,使得每个区间的数字之和都不超过给定的lim.最后的代价等于每个区间的最大值之和.求最小代价.n<=300000
定义f[i]表示前i个数划分成若干个区间的最小代价,一眼是个1D1D动态规划,猜测有决策单调性,打表发现并没有.然后也看不出什么很妙的性质. 感觉分治也许能做,推一推发现确实可以.定义solve(l,r)处理f[l...mid]到f[mid+1...r]的转移,按照最大值在左边/右边分两种情况处理,都可以线性解决.递归时要先solve(l,mid),然后处理[l,mid]到[mid+1,r]的转移,再solve(mid+1,r).细节见代码,不是很难写.
#include<cstdio> #include<algorithm> using namespace std; const int maxn=300006; typedef long long ll; int n;ll lim; ll f[maxn]; ll pre[maxn],a[maxn]; ll Min[maxn],Max[maxn],mark[maxn]; void gmin(ll &a,ll b){ if(a>b)a=b; } void solve(int l,int r){ if(l==r)return; int mid=(l+r)>>1; solve(l,mid); Min[mid]=f[mid];Max[mid]=a[mid]; for(int i=mid-1;i>=l;--i)Min[i]=min(Min[i+1],f[i]),Max[i]=max(Max[i+1],a[i]); Max[mid+1]=a[mid+1]; for(int i=mid+2;i<=r;++i)Max[i]=max(Max[i-1],a[i]); int L=l,pt=mid+1; for(int i=mid+1;i<=r;++i){ while(pre[i]-pre[L]>lim)L++; while((pt-1)>l&&Max[pt-1]<=Max[i])--pt; if(L>mid)break; gmin(f[i],Max[i]+Min[max(pt-1,L)]); } for(int i=mid+1;i<=r;++i)mark[i]=(1ll<<60); int R=r;pt=mid; for(int i=mid;i>l;--i){ while(pre[R]-pre[i-1]>lim)R--; if(R<=mid)break; while(pt+1<=r&&Max[pt+1]<=Max[i])++pt; if(pt>mid){ gmin(mark[min(pt,R)],f[i-1]+Max[i]); } } for(int i=r;i>=mid+1;--i){ gmin(f[i],mark[i]); gmin(mark[i-1],mark[i]); } solve(mid+1,r); } int main(){ scanf("%d%lld",&n,&lim); for(int i=1;i<=n;++i){ scanf("%lld",&a[i]); pre[i]=pre[i-1]+a[i]; } for(int i=1;i<=n;++i){ if(pre[i]<=lim)f[i]=max(a[i],f[i-1]); else f[i]=1ll<<60; } solve(1,n); printf("%lld\n",f[n]); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/6920650.html
相关资源：数据结构—成绩单生成器