cf1482 E. Skyline Photo
2022/5/30 23:20:15
本文主要是介绍cf1482 E. Skyline Photo,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
给定一排 n 个点,每个点有 \(h_i\) 和 \(v_i\)。把它们划分成任意数量的连续段,每个点仅属于一段,每段的价值等于段中 \(h\) 最小的点的 \(v\) 值。求最大价值和
\(h_i\) 为 1~n 的一个排列,\(-1e9\le v_i\le 1e9\)
思路:
用到单调(递增)栈的两个性质:1. 栈顶是左边小于 \(a_i\) 的最近位置;2. 对原数组的每个位置 \(j\)(不一定在单调栈里),\(j\) 右边最近的在单调栈里的位置 \(stk_t\) 就是 \([j,i]\) 中 \(a\) 最小的位置。
\(f_i\) 表示处理到 \(i\) 的最大价值。按 \(h_i\) 维护单调栈。有两种更新方式:
- 若 \(top\) 存在且与 \(i\) 放同一段,则 \(f[i]=f[stk_{top}]\);若栈为空,则 \(f[i]=v_i\);
- 设倒数第二段的最后一个位置为 \(j\),那么最后一段的价值为 \([j+1,i]\) 中最小的 \(v\),那么 \(\max\{f_j\}+v_t\),其中 \(t\) 为 \(j\) 右边最近的在单调栈中的位置
对于 2,\(stk_{top}\) 之前的信息已经在 \(f[stk]\) 中,要算的是新的一段即 \([stk_{top}+1,i-1]\) 中最大的 \(f\)。开个数组 \(mf[i]\) 记录一下处理到 \(i\) 时,弹出的所有 \(f\) 的最大值,包括 \(f_i\)
哎讲不清楚,这玩意太难描述了,摆了
ll n, h[N], v[N], f[N], mf[N]; //弹掉的东西的最大f值,包括自己 int stk[N], top; void sol() { cin >> n; for(int i = 1; i <= n; i++) cin >> h[i]; for(int i = 1; i <= n; i++) cin >> v[i]; memset(mf, -INF, sizeof mf); //初始化 for(int i = 1; i <= n; i++) { mf[i] = f[stk[top]]; while(h[stk[top]] > h[i]) mf[i] = max(mf[i], mf[stk[top--]]); f[i] = max({top ? f[stk[top]] : v[i], mf[i] + v[i]}); stk[++top] = i; mf[i] = max(mf[i], f[i]); } cout << f[n]; }
这篇关于cf1482 E. Skyline Photo的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置