博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
arc073 F many moves(dp + 线段树)
阅读量:6418 次
发布时间:2019-06-23

本文共 2855 字,大约阅读时间需要 9 分钟。

设dp[i][y]表示一个点在x[i],另一个点在y时最小要走的步数

那么有以下转移

对于y != x[i-1]的状态,可以证明,他们直接加|x[i] - x[i-1]|即可(如果有其他方案,不符合对dp的定义)

当y == x[i-1]时,它可以由其他所有状态转移过来, dp[i][x[i-1]] = min(dp[i][y] + |y - x[i]|)

把绝对值拆出来,就是需要维护一个dp[i][y] + y 和dp[i][y] - y,建立两个线段树即可。

#include 
#include
#include
#include
#define fi first#define se second#define mp make_pair#define pb push_backusing namespace std;typedef long long LL;const int maxn = 2e5 + 100;LL Plus[maxn*4], Minus[maxn*4], tag[maxn*4];inline LL abs(LL x) { return x < 0 ? -x : x; }inline void Puttag(int o, LL v){ Plus[o] += v; Minus[o] += v; tag[o] += v;}inline void Pushdown(int o){ if(!tag[o]) return; Puttag(o*2, tag[o]); Puttag(o*2+1, tag[o]); tag[o] = 0;}inline void Maintain(int o){ Plus[o] = min(Plus[o*2], Plus[o*2+1]); Minus[o] = min(Minus[o*2], Minus[o*2+1]);}inline bool Cut(int x) { return false; }inline bool Check(int x) { return true; }inline void Change(int o, int l, int r, int L, int R, LL v){ if(L > r || R < l || Cut(o)) return; if(L <= l && r <= R && Check(o)){ Puttag(o, v); return; } int mid = (l+r)/2; Pushdown(o); Change(o*2, l, mid, L, R, v); Change(o*2+1, mid+1, r, L, R, v); Maintain(o);}inline long long Query(int o, int l, int r, int L, int R, int ty){ if(L > r || R < l || Cut(o)) return 1e18; if(L <= l && r <= R){ return ty ? Plus[o] : Minus[o]; } int mid = (l+r)/2; Pushdown(o); ans = min(Query(o*2+1, mid+1, r, L, R, ty), Query(o*2, l, mid, L, R, ty)); Maintain(o); return ans;}inline void Insert(int o, int l, int r, int k, LL v, int ty){ if(l == r) { if(ty) Plus[o] = v; else Minus[o] = v; return; } int mid = (l+r)/2; Pushdown(o); if(k <= mid) Insert(o*2, l, mid, k, v, ty); else Insert(o*2+1, mid+1, r, k, v, ty); Maintain(o);}int N, Q, A, B;int x[maxn];int main(){ scanf("%d %d %d %d", &N, &Q, &A, &B); for(int i = 1; i <= Q; i++) scanf("%d", &x[i]); x[0] = B; // dp[i][x] = dp[i-1][x] + || // dp[i][x[i-1]] = all(dp[i-1][x]+|x-x[i]|) // x <= x[i] -> dp[i-1][x] + x[i] - x // x > x[i] -> dp[i-1][x] + x - x[i] memset(Plus, 1, sizeof(Plus)); memset(Minus, 1, sizeof(Minus)); Insert(1, 1, N, A, A, 1); Insert(1, 1, N, A, -A, 0); for(int i = 1; i <= Q; i++){ LL ans = min(Query(1, 1, N, 1, x[i], 0) + x[i], Query(1, 1, N, x[i]+1, N, 1) - x[i]); Change(1, 1, N, 1, x[i-1]-1, abs(x[i] - x[i-1])); Change(1, 1, N, x[i-1]+1, N, abs(x[i] - x[i-1])); Insert(1, 1, N, x[i-1], ans + x[i-1], 1); Insert(1, 1, N, x[i-1], ans - x[i-1], 0); } LL ans = 1e18; for(int i = 1; i <= N; i++){ ans = min(ans, Query(1, 1, N, i, i, 0) + i); } cout<
<

 

转载于:https://www.cnblogs.com/Saurus/p/6816770.html

你可能感兴趣的文章
linux下mongodb定时备份指定的集合
查看>>
oVirt JBAS server start failed, ajp proxy cann't server correct. ovirt-engine URL cann't open
查看>>
CDP WebConsole上线公告
查看>>
ubuntu下安装摄像头应用程序xawtv
查看>>
PostgreSQL 如何比较两个表的定义是否一致
查看>>
NSUserDefaults 使用方法
查看>>
文件编码H264编解码器性能测试
查看>>
安装wdcp的心得体会
查看>>
Nginx虚拟主机配置教程
查看>>
2014-3-9 星期天[周末计划实施总结]
查看>>
[原创].NET 分布式架构开发实战之四 构建从理想和实现之间的桥梁(前篇)
查看>>
JS重构分页
查看>>
SQL Server 索引结构及其使用(一)[转]
查看>>
[翻译] LASIImageView - 显示进度指示并异步下载图片
查看>>
Mono 3.2.7发布,JIT和GC进一步改进
查看>>
xcode添加文件时的勾选解析
查看>>
陈正冲老师讲c语言之内存的申请malloc() 和释放free()
查看>>
[翻译] MCProgressView 使用自定义图片做进度显示
查看>>
JS完成改变新闻字体大中小的显示
查看>>
.NET开发者必备的11款免费工具
查看>>