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