建立带数据库的网站,网站 快照 更新慢,关键字排名软件官网,sem工作原理正题
题目链接:https://jzoj.net/senior/#contest/show/3011/2 题目大意 n1n1n1个连续的地方#xff0c;每个地方有(a,b,c)(a,b,c)(a,b,c)。
从000开始#xff0c;每次往前选择一个不超过LLL的位置#xff0c;跳到那里并选择中间不包括起点的位置中ccc最大的地方获取这个位…正题
题目链接:https://jzoj.net/senior/#contest/show/3011/2 题目大意
n1n1n1个连续的地方每个地方有(a,b,c)(a,b,c)(a,b,c)。
从000开始每次往前选择一个不超过LLL的位置跳到那里并选择中间不包括起点的位置中ccc最大的地方获取这个位置的a,ba,ba,b。
最后要求aaa的值和bbb的值比值最大。 解题思路
显然的0/1分数规划问题二分答案midmidmid把价值变为a−b∗mida-b*mida−b∗mid然后求价值最大。
考虑dpdpdp先预处理出每个位置的cic_ici能影响到的位置(前面的最近一个比它大的ccc)。
然后dpdpdpfif_ifi表示走到iii时最大价值。
枚举一个iii,我们现在要计算fif_ifi然后定义wjw_jwj表示从jjj跳到iii时需要战斗的地方的价值。
然后用一颗线段树维护fff的区间最大值和fwfwfw的区间最大值之后我们每次单点修改fff区间修改www即可。
时间复杂度O(100nlogn)O(100n\log n)O(100nlogn)这里进行了100100100次二分。 codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
using namespace std;
const int N3e410;
const double eps1e-7;
int n,l,c[N],h[N],last[N];
double a[N],b[N],f[N],w[N];
struct Tree_Array{int t[N];void Change(int x,int val){while(xn){t[x]val;xlowbit(x);}}int Ask(int x){int ans0;while(x){ansmax(ans,t[x]);x-lowbit(x);}return ans;}
}Ta;
struct Seq_Tree{double f[N*4],w[N*4],lazy[N*4];void ReBuild(){for(int i0;i4*N;i)f[i]w[i]-1e9,lazy[i]0;return;}void Merge(int x){f[x]max(f[x*2],f[x*21]);w[x]max(w[x*2],w[x*21]);return;}void Downdata(int x){if(lazy[x]0) return;w[x*2]f[x*2]lazy[x];w[x*21]f[x*21]lazy[x];lazy[x*2]lazy[x*21]lazy[x];lazy[x]0;return;}void ChangeF(int x,int pos,int L,int R,double val){if(LR){f[x]val;return;}Downdata(x);int mid(LR)1;if(posmid) ChangeF(x*2,pos,L,mid,val);else ChangeF(x*21,pos,mid1,R,val);Merge(x);return;}void ChangeZ(int x,int l,int r,int L,int R,double val){if(LlRr){lazy[x]val;w[x]f[x]val;return;}Downdata(x);int mid(LR)/2;if(rmid) ChangeZ(x*2,l,r,L,mid,val);else if(lmid) ChangeZ(x*21,l,r,mid1,R,val);else ChangeZ(x*2,l,mid,L,mid,val),ChangeZ(x*21,mid1,r,mid1,R,val);Merge(x);return;}double Ask(int x,int l,int r,int L,int R){if(LlRr)return w[x];Downdata(x);int mid(LR)/2;if(rmid) return Ask(x*2,l,r,L,mid);if(lmid) return Ask(x*21,l,r,mid1,R);return max(Ask(x*2,l,mid,L,mid),Ask(x*21,mid1,r,mid1,R));}
}T;
bool check(double x){for(int i1;in;i)w[i]a[i]-b[i]*x;T.ReBuild();T.ChangeF(1,0,0,n,0);for(int i1;in;i){T.ChangeZ(1,last[i],i-1,0,n,w[i]);f[i]T.Ask(1,max(0,i-l),i-1,0,n);T.ChangeF(1,i,0,n,f[i]);}return f[n]0;
}
int main()
{scanf(%d%d,n,l);for(int i1;in;i){scanf(%lf%lf%d,a[i],b[i],h[i]);c[i]h[i];}sort(c1,c1n);int munique(c1,c1n)-c-1;for(int i1;in;i){h[i]m-(lower_bound(c1,c1m,h[i])-c)1;last[i]Ta.Ask(h[i]-1);Ta.Change(h[i],i);}double l0,r1000000;for(int i1;i100;i){double mid(lr)/2.0;if(check(mid)) lmid;else rmid;}double ans(lr)/2;int loc0;while(ans10) ans/10,loc;while(ans1) ans*10,loc--;printf(%.9lfe,ans);if(loc0) printf(%03d,loc);else printf(%04d,loc);return 0;
}
