首页 > 其他分享 >CF1715E Long Way Home 题解

CF1715E Long Way Home 题解

时间:2022-09-07 10:57:11浏览次数:112  
标签:limits 花费 题解 CF1715E Way Home dp dis

CF1715E 题解

题意

一个带边权无向图,可以沿着边走,需要边权的花费或从任意点 \(u\) 飞到 \(v\),需要 \((u-v)^2\) 的花费。求从点 \(1\) 到所有 \(i\) 的最少花费。最多飞 \(k\) 次。

分析

一眼最短路 + dp。

发现 \(k\) 很小,可以枚举飞的次数,对于点 \(u\),可以是走到 \(u\),这种情况可以用最短路更新答案;也可以是飞到 \(u\),此时可以 dp,\(dp_i\) 表示从 \(1\) 到 \(i\) 最小花费,转移方程很显然:

\[dp_i=\min\limits_{t=1}^n(dis_t+(i-t)^2) \]

,其中 \(dis_i\) 表示上个 \(k\) 算出的 \(1\) 到 \(i\) 最少花费。此时最外层循环 \(k\),中层循环 \(i\),内层循环 \(t\),时间复杂度 \(\mathcal{O}(kn^2)\),发现会 T,考虑优化。

发现这个式子是个典型的斜率优化形式,可以变形成:

\[dp_i=\min\limits_{t=1}^n(dis_t+(i-t)^2) \\ \ \ \ \ \ \ \ \ \ \ \ \ =\min\limits_{t=1}^n(dis_t+t^2+it)+i^2 \]

也就转化成了求 \(x=i\) 时所有直线 \(y=tx+(dis_t+t^2)\) 的最小值加上 \(i^2\) 的值。可以用李超线段树方便地求出。

code

标签:limits,花费,题解,CF1715E,Way,Home,dp,dis
From: https://www.cnblogs.com/lxy-2022/p/CF1715E-Solution.html

相关文章

  • CF1515E Phoenix and Computers 题解
    感觉这样的\(\text{dp}\)题还比较多,思路都比较的神奇。个人感觉比较像区间\(\text{dp}\)的一类变种。但又和区间\(\text{dp}\)的维护方式极不一样。对于此类\(\t......
  • P5999 [CEOI2016] kangaroo 题解
    感觉这样的\(\text{dp}\)题还比较多,思路都比较的神奇。个人感觉比较像区间\(\text{dp}\)的一类变种。但又和区间\(\text{dp}\)的维护方式极不一样。对于此类\(\t......
  • MySQL5.7完整安装教程及相关问题解决
    1 下载安装1.1下载直接官网下载https://www.mysql.com/①拉倒最下面,点community server②选择之前的版本③选5.7,通过压缩包来安装,点download1.2解压安装①下......
  • CF222C Reducing Fractions 题解
    虽然是朴素的筛法,但是跑的比希儿的Pollard-rho快。\(\mathcalO(n\sqrtn)\)的质因数分解是不行的,Pollard-rho的码量也过于麻烦,直接在线性筛里筛出每个数的最小质因子......
  • 2022/09/26小测 题解
    (本文将笔者测试时的想法及赛后想法均写出来了)题目:话说某某在\(cj\)校运会上异军突起,其实不是偶然,而是有历史原因的。时光回溯到\(XX\)年前,某某为了心中的理想,每天爬......
  • C#、IIS获取时间带星期或日期问题解决
    cmd   regedit打开注册表,进入到[HKEY_USERS\.DEFAULT\Control Panel\International]  ,然后1、将键 sDate 的值由 / 改为 - 2、将键 sShortDate 的值由 yyyy......
  • 题解【CF1316E Team Building】网络流做法
    题目传送门。一眼费用流。然后发现题解区竟然全是状压DP?????推销一下本题状压DP的题解。那么我就来yy一下我的网络流做法吧,我会尽量把网络流的想法讲得自然一点。考......
  • CSP集训题解
    CSP集训题解Summer已经完结了于是新开一个,而且旧的已经很卡了9.5CSP-S短赛1(开小灶1)T1ZZH的游戏实际上把策略想明白就很简单。以一次连续的移动为一个阶段,每个阶段都必......
  • CF1615F LEGOndary Grandmaster 题解
    CF1615FLEGOndaryGrandmaster对于两个长度为\(n\)的\(01\)串\(s,t\),你可以对\(s\)进行两种操作:把相邻两个\(0\)变成\(1\)或把相邻两个\(1\)变成\(0\),......
  • Spring Boot 项目访问hbase 编译遇到 java.io.FileNotFoundException: HADOOP_HOME an
    在window10系统下,使用idea创建了一个springboot项目,并使用hbase-client接口访问hbase,在编译的时候,遇到如下错误:  根据提示,打开链接:https://cwiki.apache.org/con......