不想多说什么,再次错过一次AK机会

T1 青蛙的烦恼

蛤の烦恼
⃢ — ⃢
设$f(i,j,k)$为在区间$[l,r]$内,位置为k时遍历所有坐标的最短路径。
$dis(i,j)$表示从点i到点j的距离
这样空间复杂度为$n^3$,1e9无法接受
不难发现k只可能为i或者为j
所以设$f(i,j,t)$为当前位置为i,区间长度为j。t=0表示区间在i右边,t=1表示区间在左边。
空间复杂度降到了$n^2$
于是就轻松解决了

代码:

T2 警卫安排

我真是太弱了
没事多叉转二叉干啥
转二叉理论上也能做,只是需要讨论4种情况。
所以不如不转



//以上截图自ppt
下面代码中,0表示安排警卫,1表示被父亲看到,2表示被儿子看到。
代码:

T3 最长上升子序列

最水的一题。
在1...k跑一遍lis,再再k+1...n跑一遍lis即可。
第二次跑lis的时候需要筛掉所有小于第k个数的元素
答案为$f[k]+max\{f[k+1...n]\}$
也可以一开始先筛掉所有小于第k个数的元素,再跑一遍lis
需要用nlogn的算法

代码:

T4 最短回文串

区间dp
设$f(i,j)$为把$[i,j]$这段子串变为一个回文串的最小代价
当$s[i]==s[j]$时$f(i,j)=f(i+1,j-1)$
否则$f(i,j)=min\{f(i+1,j),f(i,j-1)\}+1$

代码: