包头市网站建设,建设银行网络学习网站,wordpress id连续插件,站长工具seo综合查询全面解析题意 给出一个长度为n的正整数序列,要求把它划分成若干个连续的区间,使得每个区间的数字之和都不超过给定的lim.最后的代价等于每个区间的最大值之和.求最小代价.n300000 分析 定义f[i]表示前i个数划分成若干个区间的最小代价,一眼是个1D1D动态规划,猜测有决策单调性,打表发…题意 给出一个长度为n的正整数序列,要求把它划分成若干个连续的区间,使得每个区间的数字之和都不超过给定的lim.最后的代价等于每个区间的最大值之和.求最小代价.n300000 分析 定义f[i]表示前i个数划分成若干个区间的最小代价,一眼是个1D1D动态规划,猜测有决策单调性,打表发现并没有.然后也看不出什么很妙的性质. 感觉分治也许能做,推一推发现确实可以.定义solve(l,r)处理f[l...mid]到f[mid1...r]的转移,按照最大值在左边/右边分两种情况处理,都可以线性解决.递归时要先solve(l,mid),然后处理[l,mid]到[mid1,r]的转移,再solve(mid1,r).细节见代码,不是很难写. #includecstdio
#includealgorithm
using namespace std;
const int maxn300006;
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(ab)ab;
}
void solve(int l,int r){if(lr)return;int mid(lr)1;solve(l,mid);Min[mid]f[mid];Max[mid]a[mid];for(int imid-1;il;--i)Min[i]min(Min[i1],f[i]),Max[i]max(Max[i1],a[i]);Max[mid1]a[mid1];for(int imid2;ir;i)Max[i]max(Max[i-1],a[i]);int Ll,ptmid1;for(int imid1;ir;i){while(pre[i]-pre[L]lim)L;while((pt-1)lMax[pt-1]Max[i])--pt;if(Lmid)break;gmin(f[i],Max[i]Min[max(pt-1,L)]);}for(int imid1;ir;i)mark[i](1ll60);int Rr;ptmid;for(int imid;il;--i){while(pre[R]-pre[i-1]lim)R--;if(Rmid)break;while(pt1rMax[pt1]Max[i])pt;if(ptmid){gmin(mark[min(pt,R)],f[i-1]Max[i]);}}for(int ir;imid1;--i){gmin(f[i],mark[i]);gmin(mark[i-1],mark[i]);}solve(mid1,r);
}
int main(){scanf(%d%lld,n,lim);for(int i1;in;i){scanf(%lld,a[i]);pre[i]pre[i-1]a[i];}for(int i1;in;i){if(pre[i]lim)f[i]max(a[i],f[i-1]);else f[i]1ll60;}solve(1,n);printf(%lld\n,f[n]);return 0;
}转载于:https://www.cnblogs.com/liu-runda/p/6920650.html
