Codeforces Bubble Cup 8 - Finals [Online Mirror] F. Bulbo DP
F. Bulbo
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/575/problem/F
Description
Bananistan is a beautiful banana republic. Beautiful women in beautiful dresses. Beautiful statues of beautiful warlords. Beautiful stars in beautiful nights.
In Bananistan people play this crazy game – Bulbo. There’s an array of bulbs and player at the position, which represents one of the bulbs. The distance between two neighboring bulbs is 1. Before each turn player can change his position with cost |posnew - posold|. After that, a contiguous set of bulbs lights-up and player pays the cost that’s equal to the distance to the closest shining bulb. Then, all bulbs go dark again. The goal is to minimize your summed cost. I tell you, Bananistanians are spending their nights playing with bulbs.
Banana day is approaching, and you are hired to play the most beautiful Bulbo game ever. A huge array of bulbs is installed, and you know your initial position and all the light-ups in advance. You need to play the ideal game and impress Bananistanians, and their families.
Input
The first line contains number of turns n and initial position x. Next n lines contain two numbers lstart and lend, which represent that all bulbs from interval [lstart, lend] are shining this turn.
- 1 ≤ n ≤ 5000
- 1 ≤ x ≤ 109
- 1 ≤ lstart ≤ lend ≤ 109
Output
Sample Input
5 4
2 7
9 16
8 10
9 17
1 6
Sample Output
8
HINT
题意
有n个区间,你一开始站在x位置
然后n个询问,每个询问给你一个线段,是l,r区间
然后你可以选择走到x位置,花费就是距离
然后关闭这个线段的花费是你现在的位置离线段的最短距离
然后问你依次关闭这n个线段最少需要多少花费
题解:
dp咯,dp[i][j]表示第i轮我在j位置的最小花费
dp[i][j]=min(dp[i][j],dp[i-1][k]+abs(d[i]-d[k]))
然后大概单调栈或者维护一下变成o(n^2)的转移就可以AC了
代码:
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 110
#define eps 1e-9
int Num;
//const int inf=0x7fffffff; //¡ìߡ쨦¡ì¨¤¡ì¨¦¡§f¡ì3
const int inf=0x3f3f3f3f;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** struct node
{
ll x,y;
};
node a[];
vector<ll> Q;
ll dp[];
map<ll,int> H;
int main()
{
int n=read();
ll x=read();
Q.push_back(x);
for(int i=;i<=n;i++)
{
a[i].x=read(),a[i].y=read();
Q.push_back(a[i].x);
Q.push_back(a[i].y);
}
sort(Q.begin(),Q.end());
Q.erase(unique(Q.begin(),Q.end()),Q.end());
for(int i=;i<Q.size();i++)
dp[i]=abs(Q[i]-x);
for(int i=;i<Q.size();i++)
H[Q[i]]=i;
for(int i=;i<=n;i++)
{
ll tmp=dp[]-Q[];
for(int j=;j<Q.size();j++)
{
dp[j]=min(dp[j],tmp+Q[j]);
tmp=min(tmp,dp[j]-Q[j]);
}
tmp=dp[Q.size()-]+Q[Q.size()-];
for(int j=Q.size()-;j>=;j--)
{
dp[j]=min(dp[j],tmp-Q[j]);
tmp=min(tmp,dp[j]+Q[j]);
}
for(int j=;j<Q.size();j++)
{
if(Q[j]<a[i].x||Q[j]>a[i].y)dp[j]+=min(abs(Q[j]-a[i].y),abs(Q[j]-a[i].x));
}
/* for(int j=0;j<Q.size();j++)
cout<<dp[j]<<" ";
cout<<endl;*/
}
ll ans = dp[];
for(int i=;i<Q.size();i++)
ans = min(ans,dp[i]);
cout<<ans<<endl;
return ;
}
最新文章
- XPath使用示例
- nginx的pass_proxy遇到的坑
- 解决<;a>;文本本身带下划线和超链接下划线重合的问题
- loadrunner跑场景的时候出现:Abnormal termination, caused by mdrv process termination
- Eclipse代码风格
- Linux网络编程实例解析
- SQL2008-功能设置
- CLR via C#字符串和文本处理
- Vbox中Ubuntu的安装和共享文件夹设置
- python3-可变长度参数函数(*args 和 **kwargs)
- ABP的确认框
- CentOS7 安装配置rsync
- Centos install Python3
- asp.net core 自定义404等友好错误页面
- U盘或者移动银盘退出时一直显示占用中问题解决--最粗暴解决方式
- HttpWebRequest 模拟浏览器访问网站
- 缓存数据库-redis(管道)
- 瞥了一眼js
- Python学习——编程语言介绍
- MVC 中创建自己的异常处理
热门文章
- 【MySQL】通过select语句把一列数据拼接成一条字符串
- JS动态呈现还可以输入字数
- java transient简介
- Metaspace 之二--Java 8的元空间(metaspace)、metaspace监控方法
- duilib底层机制剖析:窗体类与窗体句柄的关联
- char[]数组与char *指针的区别
- Python 代码性能优化技巧
- lighttpd+fastcgi模块分析
- Subversion 1.8.1编译安装(self)
- Cocos2dx游戏源码合集(BY懒骨头+持续更新+2014.02.21)