Codeforces1249E By Elevator or Stairs?
2024-08-26 12:26:02
题意
给定整数c和数组a,b,\(a_i\)表示通过爬楼梯的方法从第\(i\)层到\(i+1\)层需要的时间,\(b_i\)表示通过坐电梯的方法从第\(i\)层到\(i+1\)层需要的时间,坐电梯前需要等c单位时间。即对于\(i<j\),通过爬楼梯的方法要从第\(i\)层到第\(j\)层,需要\(\sum_i^{j-1}a_i\)的时间,而坐电梯需要\(c+\sum_i^{j-1}b_i\)的时间。
解题思路
很明显的dp题,首先考虑最简单的dp思路,对于每次层枚举他是从之前的那一层转移过来的,即
\[dp_j=\min \left\{ dp_i + \sum_i^{j-1}a_i,dp_i+c+\sum_i^{j-1}b_i\right\}
\]
\]
这样dp的复杂度是\(O(n^2)\),显然会TLE,所以考虑优化一下
使用前缀和的方法后式子变为
\[dp_j=\min \left\{ dp_i + sa_{j-1}-sa_i,dp_i+c+sb_{j-1}-sb_i\right\}
\]
\]
对于\(j\),可以将式子中的\(sa_{j-1}\)和\(sb_{j-1}\)视为常数,那么式子变为
\[dp_j=\min \left\{ \min\left\{dp_i - sa_i\right\} + sa_{j-1},\min \left\{dp_i - sb_i \right\}+c+sb_{j-1}\right\}
\]
\]
记录\(dp_i - sa_i\)和\(dp_i - sb_i\)的最小值,每次更新即可,复杂度\(O(n)\)
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int n,c,a[maxn],b[maxn];
ll dp[maxn];
int main()
{
scanf("%d %d",&n,&c);
for(int i=1;i<=n-1;i++)scanf("%d",&a[i]),a[i]+=a[i-1];
for(int i=1;i<=n-1;i++)scanf("%d",&b[i]),b[i]+=b[i-1];
ll A=0,B=0;
printf("%lld",dp[1]);
for(int i=1;i<=n-1;i++){
dp[i]=min(B+b[i]+c,A+a[i]);
A=min(A,dp[i]-a[i]);
B=min(B,dp[i]-b[i]);
printf(" %lld",dp[i]);
}
return 0;
}
最新文章
- B样条曲线曲面(附代码)
- C# 如何获取当前应用程序的上一级路径
- Centos7 设置Swap分区
- Spring学习笔记之初始化和销毁方法的调用次序
- Hive 复习
- DBA常用SQL之会话与等待事件
- Jasper_table_pass parameter to table component
- xtrabackup 链接不上MySQL的问题
- HTML5 &; CSS3初学者指南(3) – HTML5新特性
- Win10家庭版设置桌面右键更换桌面壁纸
- Eclipse 新建jsp文件报错问题
- golang中使用ETCD
- 学习笔记(一)HTML基础
- Netty源码分析(五):EventLoop
- github上传流程图记录
- pythonのsqlalchemy外键关联查询
- vue全局路由守卫beforeEach
- 前端通信:ajax设计方案(十)--- 完善Promise A+规范,增加mock数据功能
- SED单行脚本快速参考(Unix 流编辑器)(转)
- IOS网络篇1之截取本地URL请求(NSURLProtocol)