T1

青蛙的烦恼

题目描述:池塘中有 n 片荷叶恰好围成了一个凸多边形,有一只小青蛙恰好站在 1 号荷叶上,小青
蛙想通过最短的路程遍历所有的荷叶(经过一个荷叶一次且仅一次),小青蛙可以从一片荷
叶上跳到另外任意一片荷叶上。
题目分析
青蛙怎么烦恼的我不知道,反正我很烦恼。
我有一句那啥不知当讲不当讲。
想了一个半小时,
好吧,咱们仔细看看,如果我们用f(i,j)表示从i到j全部遍历一遍,最后停在i处的最短路,g(i,j)表示停在j处。
对于i到j的所有点的最好路径,如果起点和终点中有一个是i或者j,那么就可以转化为f(i,j)或者g(i,j),那如果起点和终点都不是i或者j呢?没关系,在动态规划的过程中要用到的就只有i或者j了。
代码

T2

警卫安排

题目描述:一个重要的基地被分为 n 个连通的区域。出于某种神秘的原因,这些区域以一个区域为
核心,呈一颗树形分布。
在每个区域安排警卫所需要的费用是不同的,而每个区域的警卫都可以望见其相邻的区
域,只要一个区域被一个警卫望见或者是安排有警卫,这个区域就是安全的。你的任务是:
在确保所有区域都是安全的情况下,找到安排警卫的最小费用。
题目分析
还是不难的,就是麻烦了点。
用f(i,0)表示i节点上安放了警卫
用f(i,1)表示i节点被其父亲节点看到
用f(i,2)表示i节点被其儿子节点看到
那么:
$$f(i,0)= \sum min(f(son,0),f(son,1),f(son,2));$$
$$f(i,1)= \sum min(f(son,0),f(son,2));f$$
$$f(i,2)= \sum min(f(son,0),f(son,2))+f(k,0);$$,k是i的子节点之一
代码

T3

最长上升子序列

题目描述:LIS 问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子
序列,你还能解决吗?
给出一个长度为 N 整数序列,请求出它的包含第 K 个元素的最长上升子序列。
例如:对于长度为 6 的序列(2,7,3,4,8,5),它的最长上升子序列为(2,3,4,5),但如果
限制一定要包含第 2 个元素,那么满足此要求的最长上升子序列就只能是(2,7,8)了。
题目解析
可以在k之前跑一遍最长上升子序列,去掉大于k的,然后在k后面跑一遍,去掉小于k的。当然也可以把这两步合并,见代码

T4

最短回文串

题目描述:如果一个字符串正过来读和倒过来读是一样的,那么这个字符串就被称作回文串。例如
abcdcba,abcddbca 就是回文串,而 abcdabcd 不是。
你要解决的问题是:对于任意一个字符串,输出将这个字符串变为回文串需要插入的最
少字符个数,比如,ab3bd 只需要插入 2 个字符就可以变为一个回文串
题目分析:用f(i,j)表示从i到j的字符串变成回文串的最少改变次数,那么如果a[i]==a[j],则f(i,j)=f(i+1,j-1);
如果不等于的话,可以往左边加一个字母或者往右边加一个字母则:f(i,j)=min(f(i,j-1),f(i+1,j));
代码

现在我们回到标题,题目都很简单是吧,那么动规5是怎么挂的呢?
大约是蠢吧。