[TJOI2007] 线段 (动态规划)
2024-09-05 18:46:07
题目链接
Solution
传统的线性 \(dp\) .
\(f[i][0]\),\(f[i][1]\) 分别表示最后一次在 \(i\) ,然后在 左边或者右边的最小步数.
然后就每次根据上一次左边和右边的状态转移过来.
Code
#include<bits/stdc++.h>
#define N 20001
#define in(x) x=read()
using namespace std;
int l[N],r[N],n,ans=0x3f3f3f3f;
int v[N],f[N][2];
int read()
{
char ch=getchar(); int f=1,w=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return f*w;
}
int main()
{
in(n);
for(int i=1;i<=n;i++)
in(l[i]),in(r[i]);
memset(f,127,sizeof(f));
f[1][0]=r[1]*2-l[1]-1;
f[1][1]=r[1]-1;
for(int i=2;i<=n;i++)
{
f[i][0]=min(f[i][0],f[i-1][0]+abs(l[i-1]-r[i])+r[i]-l[i]+1);
f[i][0]=min(f[i][0],f[i-1][1]+abs(r[i-1]-r[i])+r[i]-l[i]+1);
f[i][1]=min(f[i][1],f[i-1][0]+abs(l[i-1]-l[i])+r[i]-l[i]+1);
f[i][1]=min(f[i][1],f[i-1][1]+abs(r[i-1]-l[i])+r[i]-l[i]+1);
}
ans=min(f[n][1]+n-r[n],f[n][0]+n-l[n]);
cout<<ans<<endl;
}
最新文章
- POJ1742Coins(并不理解是什么意思)
- msys2安装
- 【转】向HTML中插入视频并兼容所有浏览器的方法
- bzoj4457: 游戏任务--双层01背包
- How to upgrade workflow assembly in MOSS 2007
- springMVC导出 CSV案例
- PHP常用文件函数和目录函数整理
- 移动开发:初学 iOS-UIViewController 心得
- 【MVC】过滤器
- 超炫HTML5 SVG聊天框拖拽弹性摇摆动画特效
- Vector2.Angle 的 bug
- .net Kafka.Client多个Consumer Group对Topic消费不能完全覆盖研究总结(一)
- [Python] wxPython 状态栏组件、消息对话框组件 学习总结(原创)
- Django Admin初识
- Scala学习(六)练习
- [Android Pro] AndroidX了解一下
- tensorflow模型持久化保存和加载
- 获得Variant类型
- 解题:SDOI 2014 数表
- HALCON形状匹配(转)
热门文章
- JAVA / MySql 编程—— 第四章 高级查询(二)
- thinkphp5,单图,多图,上传
- PHP时间日期操作增减(date strtotime) 加一天 加一月
- Zookeeper+Kafka的单节点配置
- HAN模型理解2
- iOS-cell的封装和重用
- WPF点击不同界面上的按钮实现界面切换
- CodeForces 778D Parquet Re-laying 构造
- Java算法求最大最小值,倒序,冒泡排序,斐波纳契数列,日历一些经典算法
- Spring进阶—如何用Java代码实现邮件发送(一)