首页 > 其他分享 >[JSOI2016]灯塔

[JSOI2016]灯塔

时间:2022-12-14 20:57:12浏览次数:31  
标签:p2 return JSOI2016 int mid 1000001 灯塔 dp

链接:https://www.luogu.com.cn/problem/P5503 题目描述:对于每一个$i$,求出$h_{j}-h_{i}+\lceil\sqrt|i-j|\rceil$的最大值。 题解:令第$i$个数的答案为$dp_{i}$,打表可以发现$h$具有决策单调性。这一类决策单调性可以采用整体二分的方式求得决策点范围,由于决策点可能相同,所以不能先取整。 ``` #include #include #include using namespace std; double dp[1000001],dp2[1000001],f[1000001]; long long h[1000001],n,p[1000001],p2[1000001]; void solve(int l,int r,int L,int R) { int mid=(l+r)/2; for (int i=R;i>=L;--i) if (i<mid&&h[i]+f[mid-i]>dp[mid]) { dp[mid]=h[i]+f[mid-i]; p[mid]=i; } if (l==r) return; solve(l,mid,L,p[mid]); solve(mid+1,r,p[mid],R); return; } void solve2(int l,int r,int L,int R) { int mid=(l+r)/2; for (int i=R;i>=L;--i) if (i>mid&&h[i]+f[i-mid]>dp2[mid]) { dp2[mid]=h[i]+f[i-mid]; p2[mid]=i; } if (l==r) return; solve2(l,mid,L,p2[mid]); solve2(mid+1,r,p2[mid],R); return; } int main() { cin>>n; for (int i=1;i<=n;++i) { cin>>h[i]; dp[i]=-1e18; } for (int i=1;i<=n;++i) f[i]=sqrt(i); solve(1,n,1,n); solve2(1,n,1,n); for (int i=1;i<=n;++i) cout<<(int)(ceil(max(max(dp[i],dp2[i])-h[i],(double)(0))))<

标签:p2,return,JSOI2016,int,mid,1000001,灯塔,dp
From: https://www.cnblogs.com/zhouhuanyi/p/16983506.html

相关文章

  • “灯塔工厂”示范中国制造业未来
    “灯塔工厂”示范中国制造业未来工人在阿里巴巴犀牛智造工厂车间忙碌(2020年9月摄)张璇摄/本刊◇由树根互联打造的“根云平台”根据工厂里36000多个数据采集点收集的工业......
  • [JSOI2016]最佳团体
    [JSOI2016]最佳团体#include<bits/stdc++.h>usingnamespacestd;inlineintread(){ charch=getchar(); ints=0,f=1; for(;!isdigit(ch);ch=getchar())if(ch=='......
  • 【POI2011】Lightning Conductor_【JSOI2016】灯塔(决策单调性优化dp)
    首先进行变形:\[\begin{aligned}a_j&\leqa_i+p-\sqrt{|i-j|}\\p&\geq\max_{j=1}^n\left(a_j+\sqrt{|i-j|}\right)-a_i\end{aligned}\]把\(|i-j|\)拆为\(\max(i-j......
  • Taro小程序接入灯塔分析SDK统计PV
    思路:不修改代码,在一个全局都需要访问的地方埋点。最好能获取到用户的访问路径。经过测试发现,Taro的navigateTo,redirectTo,switchTab,navigateBack都可以通过重现实现......