[AHOI2005]病毒检测

[AHOI2005]病毒检测
这个可以给出O(n^3)复杂度的代码,肯定就是O(n^3)啦,没有质疑的空间了。那么有什么代码开一跑怎么快呢,DP,DFS,贪心。
这里的话我们就用DP解一下这题
F[i][j]代表母串匹配i个,字串匹配到j个时可不可以匹配到。
然后更新一下,注意*要特判一下,因为他可以匹配很多个字符。 ......  查看更多

「AHOI / HNOI2018」道路

2018-4-13模拟赛:道路
原本是最水的一题又因为题目啰嗦,题序不对好像当场只有两人A掉了呢。
但是这题的确很水,可惜我当场也是没想出来。
这题就是记忆化搜索啦!
我们用f[k][x][y]代表现在第k个节点,翻修x条公里,翻修y条铁路的最小代价,然后记忆化一下之后状态转移
f[k][x][y]=min(f[lc][x][y]+f[rc][x][y+1],f[lc][x+1][y]+f[rc][x][y]),lc,rc分别代表左右子树节点的编号。 ......  查看更多