发布于

UVa-10917 Walk Through the Forest [最短路+DP/记忆化递归]

题目：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1858

uva访问不到的可以去vjudge上：https://vjudge.net/problem/UVA-10917

题目大意是说有两个点1，2. 从1出发走到2，每次只走可以make progress的路径， 所谓的make progress的A到B的边指的是从存在B到2的某条路比A到2的任何路的长度都要小，实际上就是B到2的最短路比A到2的最短路要短。可以用单源最短路求出2出发的所有最短路，然后从1开始做一个DFS就可以求出正确答案。但是需要注意的就是这个DFS要记忆化一下，否则会TLE

继续阅读“UVa-10917 Walk Through the Forest [最短路+DP/记忆化递归]”
发布于

CodeForces – 727E [字符串哈希]

题目传送门： http://codeforces.com/problemset/problem/727/E

题目大意是说给出n个长度均为k的字符串（两两不同），它们可以排成一个环，这些字符串以排列好的一个环的形式给出。问能否从​\( g(g\ge n) \)​个长度为k的字符串（两两不同）中选出n个形成之前给出的字符串环排列。如果可以请给出环排列的一个线排列。

继续阅读“CodeForces – 727E [字符串哈希]”
发布于

碎碎念的年终总结

总的说来2018年的精彩程度超越了之前我所经历过的年份。 在我看来这是一个非常值得纪念的一年， 所以才有了这样一篇不那么精彩的总结。 毕竟是涉及自己最珍贵的经历的记录， 我会在这篇文章里面尽量避免academic style的， 不过说到底我也不会什么正经的academic style罢了。

继续阅读“碎碎念的年终总结”
发布于

动态规划的斜率优化

在某些情况下, 动态规划的转移数目过多导致即使使用动态规划算法也会令复杂度过高. 但往往, 在某些情况下状态转移方程具有某些特别的性质, 对转移方程进行变形就可以转化为某种斜率的形式, 利用斜率的几何意义构造凸集, 通过维护一个单调双端队列使得​\( O(n^2) \)​复杂度的状态转移优化至​\( O(n) \)​.

下面结合几个例子讲一讲。

继续阅读“动态规划的斜率优化”