1024问

CodeForces - 1313C2 Skyscrapers (hard version)(单调栈+dp)

Radinka ·
更新时间:2024-09-20
· 602 次阅读

题目链接：点击查看

题目大意：给出 n 块连续的空地可以建造摩天大楼，政府有规定，每块地最高只能建 a[ i ] 的高度，同时每栋大楼需要满足一个规则，即每栋大楼的两侧不允许同时存在比自己高的大楼，输出一种方案，使得总高度之和最大

题目分析：C1题目的数据范围是 1e3 ，直接两层 for 暴力枚举每个位置作为最高点就可以了，没有难度的暴力就不多说了，直接说一下C2题目的 5e5 该如何处理吧

看到 5e5 这个数字，再看到题目给出了 3 秒的时限，第一反应肯定是摒弃 n * n 的算法，从而需要思考能否在O(n),O(nlogn)或O(nsqrt(n))中做出选择，赛后看牛客的群中有大牛用了nsqrt(n)分块的做法做出来了所以提一嘴。。其实比赛的时候队友已经想出该如何用 dp O(n) 维护答案了，设dp1[ i ]为正着到第 i 个位置为最高点的最大高度和，dp2[ i ]为反着到第 i 个位置为最高点的最大高度和，预处理完两个dp数组后，就可以O(n)枚举每个位置作为最高点，并且O(1)获得此时的贡献了，此时确定好最高点的位置剩下的输出就不多说了，现在的问题转换为了如何预处理出两个dp数组，其实不难，以dp1为例，当处理到dp[ i ]时，我们只需要找到一个位置 pos ，这个位置是位置 i 左边第一个比 a[ i ] 小的位置，此时 dp[ i ] = dp[ pos ] + ( i - pos ) * a[ i ] ，怎么解释呢，因为 pos 是位置 i 左侧第一个比 a[ i ] 小的位置，所以区间 ( pos , i ] 内的所有高度一定是大于等于 a[ i ] 的，因为我们的dp数组是求以点 i 为最高点时的最大高度和，所以点 i 的高度肯定是最大高度了，显然区间 ( pos , i ] 内的所有点都赋值为 a[ i ] 是最优的，而此时再累加上dp[ pos ]的答案便是当前点 i 的答案了

剩下的问题就变的很简单了，如何求出每个点左边以及右边第一个小于自己的位置呢，单调栈的基础应用，直接套上模板，O(n)维护出位置就可以了，总的时间复杂度为O(n)，带着一点常数无伤大雅

代码的话别看着很长，其实复用的部分很多，实际的编程复杂度充其量也只有一半多一点吧，剩下的都是CV大法了

代码：
 

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=5e5+100; LL a[N],dp1[N],dp2[N]; int l[N],r[N]; int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false); int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",a+i); a[0]=a[n+1]=-inf; stackst; st.push(0); for(int i=1;i=a[i]) st.pop(); l[i]=st.top(); st.push(i); } while(st.size()) st.pop(); st.push(n+1); for(int i=n;i>=1;i--) { while(st.size()&&a[st.top()]>=a[i]) st.pop(); r[i]=st.top(); st.push(i); } for(int i=1;i=1;i--) dp2[i]=dp2[r[i]]+(r[i]-i)*a[i]; LL mmax=-inf,mark; for(int i=1;i<=n;i++) if(mmax<dp1[i]+dp2[i]-a[i]) { mmax=dp1[i]+dp2[i]-a[i]; mark=i; } dequeans; ans.push_back(a[mark]); LL pre=a[mark]; for(int i=mark-1;i>=1;i--) { pre=min(pre,a[i]); ans.push_front(pre); } pre=a[mark]; for(int i=mark+1;i<=n;i++) { pre=min(pre,a[i]); ans.push_back(pre); } for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); return 0; }
作者：Frozen_Guardian



dp version CodeForces c2

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
disabled不可输入的值无法传递到action层
Francesca 2020-12-04
695
ASP.NET之Response.Cookies.Remove 无法删除COOKIE的原因
Kefira 2020-07-10
864
Linux中的curl命令详解
Ady 2021-03-05
996
asp 使用正则表达式替换word中的标签，转为纯文本
Iona 2021-07-23
518
redis requires ruby version2.2.2的解决方案
Madeline 2021-12-16
1127
C++数位DP复杂度统计数字问题示例详解
Zada 2021-12-16
1498
c++基础算法动态DP解决CoinChange问题
Beth 2021-12-16
119
详解树形DP
Bliss 2021-12-16
310
详解DAG上的DP
Viridis 2021-12-16
355
Win10 Version 1909累积更新补丁KB4601315：修复诸多 BUG
Jacinda 2022-01-15
397
os x yosemite dp6下载 os x 10.10 dp6官方下载地址
Brigitte 2022-02-21
574
os x yosemite dp5下载地址 os x 10.10 dp5更新内容
Vanna 2022-02-21
1092
未能加载文件或程序集 Microsoft.Office.Interop.Excel, Version=14.0.0.0
Isis 2022-03-10
382
详解MybatisPlus中@Version注解的使用
Alanni 2022-06-16
480
使用pip下载时提示You are using pip version 8.1.1, however version 22.1 is available.错误解决
Querida 2022-08-11
1287
android中px、sp与dp之间进行转换详解
Miette 2022-08-21
1484
C语言 深入理解动态规划之计数类DP
Fern 2022-10-24
1277
C语言深入探究动态规划之区间DP
Dabria 2022-10-24
944
C语言深入探究动态规划之线性DP
Tricia 2022-10-24
913
C语言数学问题与简单DP01背包问题详解
Elsa 2022-10-24
1578