题目链接https://www.luogu.org/problemnew/show/P1282 分析题目中给的状态很少,我们先考虑最后能否得到一个值,这样的话我们可以比较容易的想出状态转移方程 用$f[i][j]$表示能否用前$i$张骨牌旋转或不旋转得到上下之差值为$j$，$a[i],b[i]$分别为第$i$张骨牌的上下点数,这样转移方程为 f[i+1][j+a[i+1]-b[i+1]]=f[i+
题目链接https://www.luogu.org/problemnew/show/P1356 分析这道题一个很显然的想法就是$f[i][j]$表示能否利用前$i$个数进行运算得到$j$,但是这意味着你可能需要一个庞大的$bool$数组加上较大的时间复杂度. 于是根据同余的性质我们用$f[i][j]$表示能否利用前$i$个数进行运算得到膜$k$等于$j$的一个数,这样我们只需要一个大小为$f[ma
题目链接https://www.luogu.org/problemnew/show/P2687 分析题目要求你买最多天数的股票,很容易发现实际上就是求最长下降子序列,但是怎么计算方案数有点烦人 我们用$f[i]$表示以第$i$天结尾的最长下降子序列长度,$g[i]$表示以转移到以第$i$天结尾的最长下降子序列可用的方案数 那么我们可以这样进行状态转移: 12345678910for(ri i=1;
题目链接:https://www.luogu.org/problemnew/show/CF10D 方法一分析$LCS$和$LIS$已经成烂大街的知识了,可是当这两个合并起来成为$LCIS$,解决的方式方法也多了起来. 首先有种最朴素的$O(N^4)$方法,$f[i][j]$表示A串第$i$个字母和B串第$j$个字母结尾的状态中$LCIS$的长度,那么 那么如果$a[i]==b[j]$,$f[
题目链接 https://www.luogu.org/problemnew/show/P2502 分析 一个很$naive$的做法是从$s$到$t$双向BFS这当然会TLE 这时我就有个想法就是二分套二分边下标来求得一个比值,同时排序后从小到大枚举每一条边作为最小值,同时再枚举每一条边,如果边权之比小于比值就连起来用并查集维护连通性,可是这个时间复杂度$O(m^2 log^2m \ \alpha(
题目链接https://cn.vjudge.net/problem/UVA-571 分析刚做了道倒水问题的题想看看能不能水二倍经验,结果发现了这道题 题意翻译:https://www.cnblogs.com/devymex/archive/2010/08/04/1792288.html 设A容量$x$,B容量$y$ 我们把将水倒入A视为$+x$,将倒空B视为$-y$,若A满,就倒入B视为$-x$
题目链接https://cn.vjudge.net/problem/UVA-10603 分析经典的倒水问题,直接BFS. 对于喜闻乐见的状态判重,一开始想来个哈希函数把一个三元组映射成一个数，后面发现数据很小直接三维数组，后面又发现总水量是固定值,直接二维$bool$数组就好了 然后每次取出状态更新下答案,搜索时就是枚举将哪个杯子的水倒入哪个杯子还是很好写的，记得要状态还原 忽然发现最近只会写写水
题目链接https://www.luogu.org/problemnew/show/P1032 分析这题本来很裸的一个BFS，发现其中的字符串操作好烦啊。然后就翻大佬题解发现用STL中的string居然变得这么简洁！！！ 各种string操作请看另一位大佬博客，写得很全啊： https://www.cnblogs.com/rvalue/p/7327293.html#commentform 其实我们
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3085 分析大意就是一个男孩和一个女孩在网格里,同时还有两个鬼,男孩每轮走三步，女孩每轮走一步，与鬼曼哈顿距离不超过2*轮数的区域都被鬼占领，问男孩女孩最少多少轮相遇？ 这题显然用双向BFS,男孩每轮拓展3次,女孩每轮拓展1次,一个记录女孩走过哪些地方，另一个记录男孩，有个地方被两人都走过就输出答案 然后
学习笔记—八数码问题先看道题目https://www.luogu.org/problemnew/show/P1379 分析经典的八数码问题,有双向BFS和$IDA$ 的方法，这里使用的是$A$ 启发式搜索. 简要介绍一下$A$ ,就是对于搜索的每一个状态设计一个评估函数$f(state)$,表示当前状态$state$到目标状态所需代价的估计值;还有一个$g(state)$,表示当前状态$state