2018.12.1 万圣节的小L
2024-09-01 01:28:05
我回来啦
试题描述
|
今天是万圣节,小L同学开始了一年一度的讨要糖果游戏,但是在刚刚过去的比赛中小有成就的他打算给自己增加一点难度:如果没有讨到每一家的糖果就算输。 已知小L共有n(n不大于10000)个邻居,他们都在同一条街上(可以近似看成一条直线),第i个邻居的坐标是xi。L同学的妈妈会在一开始把他送到任意邻居的门前。现在已知所有邻居会在di时间后休息(休息以后不能再去打扰),求访问完所有点的最短时间,如果无解输出“No solution”。 |
输入
|
输入第一行为一个正整数表示n,接下来n行,每行两个用空格隔开的数,分别表示第i个邻居的位置和休息时间。
|
输出
|
输出一个数,表示最短时间,无解输出“No solution”。
|
输入示例
|
5
1 3 3 1 5 8 8 19 10 15 |
输出示例
|
11
|
看起来是一个搜索或者dp
然鹅发现搜索会TLE
考虑dp:
为了转移我们存储的数据我们不能采用普通的区间dp
我们不难发现,为了遍历直线上的每一个点,其中一个端点一定是最后经过的点(自己可以推一下)
所以我们用dp[i][j][0]表示从i到j结束在左端点的最短时间
用dp[i][j][1]表示从i到j结束在右端点的最短时间
于是对于i到j+1的区间在合法范围内就有了两种选择:从i到j区间转移或者从i-1到j+1区间转移
但是发现空间开不下于是我们换一种存储方式
为了节省空间我们只存储区间起点(压缩一维存储区间长度奇数偶数)
于是我们又有了四种转移方式:
对于从i到j的区间,从i-1到j转移(两种)或者从i到j-1转移(两种)
关于转移:
对于区间dp来讲,无后效性体现在从一步到下一步的转移
所以转移的代价是从结束时间到下一个节点的距离
关于合法:主要就是时间不要超过
上代码
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int n,dp[][][],xx[],d[],nx;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d",&xx[i],&d[i]);
for(int i=;i<=n;i++)dp[][i][]=dp[][i][]=;
for(int i=;i<n;i++)
{
int x=nx;nx^=;
for(int j=;j<=n-i;j++)
{
dp[nx][j][]=min(dp[x][j+][]+xx[j+]-xx[j],dp[x][j+][]+xx[j+i]-xx[j]);
dp[nx][j][]=min(dp[x][j][]+xx[j+i]-xx[j],dp[x][j][]+xx[j+i]-xx[j+i-]);
if(dp[nx][j][]>d[j])dp[nx][j][]=INF;
if(dp[nx][j][]>d[i+j])dp[nx][j][]=INF;
}
}
int ans=min(dp[nx][][],dp[nx][][]);
if(ans>=INF)puts("No solution");
else printf("%d",ans);
return ;
}
最新文章
- C++常用特性原理解析
- DDD实施经验分享—价值导向、从上往下进行(圈内第一个吃螃蟹DDD实施方案)
- 解决win7下PIL无法打开图片的问题
- Android自定义UI模板
- 2016年12月19日 星期一 --出埃及记 Exodus 21:14
- Qt resizeEvent 控件居中设置
- JavaScript 类
- java学习面向对象值static
- JAX-WS + Spring 开发webservice
- 【hihoCoder第十四周】无间道之并查集
- 一段代码说明javascript闭包执行机制
- 资深小白带你走进OS Memory
- 每周.NET前沿技术文章摘要(2017-05-10)
- SpringBoot打包项目成war包,并部署到服务器的tomcat上
- 浅谈AndroidGPU过度绘制、GPU呈现模式分析及相关优化
- Codeforces Gym100187C Very Spacious Office 贪心 堆
- sublime 将打字内容放在屏幕中央
- ajax参考增删改查
- Android sdk 目录结构说明
- js前台取用后台传递过来的map集合方式