DP

由图可以知道优先级相同的点都在一个“7”字形中

所以在走当前的优先级的点时最好从右下的点走到左上的点,或从从左上的点走到右下的点

那记dp[i][0]表示在走完第i个优先级时停在左上角的那个点

dp[i][1]表示在走完第i个优先级是停在右下角的那个点

答案就是max(dp[最大优先级][0],dp[最大优先级][1])

还有要将优先级离散化或者分组

注意边界条件,和转移方程即可

#include <bits/stdc++.h>
#define inf 1e9
#define ll long long
using namespace std;
ll n,dp[210000][2],w,up[210000],down[210000];
struct node
{
ll x,y,level;
}sh[210000];
node start;
ll m_max(ll a,ll b)
{
if (a>b)
return a;
else
return b;
}
ll m_min(ll a,ll b)
{
if (a<b)
return a;
else
return b;
}
ll m_abs(ll x)
{
if (x<0)
return -x;
else
return x;
}
bool cmp(node a,node b)
{
if (a.level!=b.level)
return a.level<b.level;
else
{
if (a.x!=b.x)
return a.x<b.x;
else
return a.y>b.y;
}
}
ll dis(node a,node b)
{
return m_abs(a.x-b.x)+m_abs(a.y-b.y);//求曼哈顿距离
}
int main()
{
scanf("%lld",&n);
for (ll i=1;i<=n;i++)
{
scanf("%lld%lld",&sh[i].x,&sh[i].y);
sh[i].level=m_max(sh[i].x,sh[i].y);
}
sort(sh+1,sh+1+n,cmp);
ll kind;
kind=sh[1].level;
w=1;
up[w]=1;
for (ll i=2;i<=n;i++)
{
if (kind!=sh[i].level)
{
down[w]=i-1;
w++;
up[w]=i;//将每一个优先级的左上角和右下角的点的下标处理出来
kind=sh[i].level;//进行分组
}
}
down[w]=n;
start.x=0;start.y=0;
for (ll i=1;i<=w;i++)
dp[i][0]=dp[i][1]=inf;
dp[1][1]=dis(start,sh[up[1]])+dis(sh[up[1]],sh[down[1]]);
dp[1][0]=dis(start,sh[down[1]])+dis(sh[up[1]],sh[down[1]]);
for (ll i=2;i<=w;i++)
{//简单的转移
dp[i][0]=m_min(dp[i-1][0]+dis(sh[up[i-1]],sh[down[i]]),dp[i-1][1]+dis(sh[down[i-1]],sh[down[i]]))+dis(sh[up[i]],sh[down[i]]);
dp[i][1]=m_min(dp[i-1][0]+dis(sh[up[i-1]],sh[up[i]]),dp[i-1][1]+dis(sh[down[i-1]],sh[up[i]]))+dis(sh[up[i]],sh[down[i]]);
}
printf("%lld\n",m_min(dp[w][0],dp[w][1]));
}

最新文章

  1. Maven :No goals have been specified for this build
  2. 【如何快速的开发一个完整的iOS直播app】(美颜篇)
  3. ROW_NUMBER、RANK()、DENSE_RANK()和OVER的使用
  4. js020-JSON
  5. 详细解读PHP时区修改正确方法
  6. sencha/extjs 动态创建grid表格
  7. socket浅谈
  8. 9.java.lang.ClassCastException
  9. Websphere(was)与Weblogic部署EJB的注意项
  10. linux下expect命令实现批量ssh免密
  11. nginx反向代理二级域名注意事项
  12. webpack4.0各个击破(5)—— Module篇
  13. tr 设置margin、padding无效
  14. Linux_Centos7_设置MySql定时备份
  15. Google浏览器设置变更默认搜索引擎为百度
  16. 【Android】3.20 示例20—全景图完整示例
  17. nexus 增加代理仓库 无法搜到snapshot的jar包 解决方法
  18. 使用cmd命令登录mysql数据库时报2013-Lost connection to MYSQL server at &#39;waiting for initial communication packet&#39;,system error:0
  19. 判断字符串是否为回文 python
  20. eclipse - maven使用国内镜像

热门文章

  1. 从字节码层次看i++和++i
  2. Fabric1.4.4 多机solo共识搭建
  3. devops-jenkins部署和基本使用
  4. Github个人首页美化指北
  5. Linux就该这么学28期——Day05 vim编辑器与Shell命令脚本 (yum配置 网卡配置)
  6. selenium元素定位学习笔记
  7. 【C语言C++编程入门】——编译机制和语言标准!
  8. php查看进程
  9. SOAP调用Web Service
  10. MVC查询