Codeforces 354D - Transferring Pyramid(DP)
2022/1/22 23:08:52
本文主要是介绍Codeforces 354D - Transferring Pyramid(DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Codeforces 题面传送门 & 洛谷题面传送门
好久没写题解了,写一篇找找感觉吧(
首先发现答案不超过 \(3k\),也就是说,我们选择的三角形的高度是 \(\mathcal O(\sqrt{k})\) 级别的,准确来说,\(\sqrt{6k}\)。故对于 \(y>\sqrt{6k}\) 的点我们肯定会选择花费 \(3\) 的代价使用 1 操作将其搞定。
接下来考虑怎样处理 \(y\le\sqrt{6k}\) 的部分的贡献。考虑从右到左处理,设 \(dp_{i,j}\) 表示目前钦定了 \(i\) 之后的部分的高度,第 \(i\) 列的高度为 \(j\) 的最小代价,那么有转移 \(dp_{i,j}+w(i-1,j)\to dp_{i-1,j+1},dp_{i,j}+w(i-1,k)+\dfrac{k(k+1)}{2}\to dp_{i-1,k}\),其中 \(w(i,j)=3\sum\limits_{x_k=i,y_k>j}1\)
时间复杂度 \(n\sqrt{k}\)。
const int MAXN = 1e5; const int INF = 0x3f3f3f3f; int n, k, dp[MAXN + 5]; vector<int> vec[MAXN + 5]; int main() { scanf("%d%d", &n, &k); for (int i = 1, x, y; i <= k; i++) scanf("%d%d", &x, &y), vec[y].pb(n - x + 1); for (int i = n; i; i--) { int lim = min(800, n - i + 1); for (int pos : vec[i]) { for (int j = 0; j <= min(lim, pos - 1); j++) { chkmin(dp[pos], dp[j]); dp[j] += 3; } } static int tmp[MAXN + 5]; tmp[0] = dp[0]; for (int j = 0; j <= lim; j++) { tmp[j + 1] = dp[j]; chkmin(tmp[0], dp[j] + j * (j + 1) / 2 + 2); } for (int j = 0; j <= lim + 1; j++) dp[j] = tmp[j]; } printf("%d\n", dp[0]); return 0; }
这篇关于Codeforces 354D - Transferring Pyramid(DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验