此文为个人笔记，大学时候的总结难免有错，不代表本人目前水平[手动doge] (by 2021)

本来这总结已经被我从网络上删除了，看在可能是本文迄今为止唯一读者老田园的份上重新发布，方便老人查阅。

01背包

有n种物品，一个承重量为m的背包，每种物品最多只能拿一个或者不拿，且每个物品都有价值v[i]和重量w[i]，问怎么拿使背包内物品价值最大。

定义dp[i][j]表示走到第i个物品，背包重量为j时的价值。

转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

dp[i-1][j]表示不拿当前物品，背包重量为j时的价值

RMQ区间最值查询，对于长度为n的数组A[]。

RMQ(i,j)，返回数组A区间[i , j]内的最大值或最小值。

思路：

(线段树也是可以的

ST算法：

O(nlogn)预处理，O(1)查询

求模式串在目标串中出现的次数和位置

next数组的一些性质

KMP最小循环节、循环周期：

定理：假设S的长度为len则S存在最小循环节，对S构造next数组，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。

回文串是指是正着读和反着读都一样的字符串，比如abcba。

最长回文子串是指在一个字符串中能找到的最长回文串，如这个字符串最长回文字串是最后6个字符：abacacbaaaab

哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）

小乐乐搭积木

链接：https://ac.nowcoder.com/acm/contest/301/B

来源：牛客网

题目描述

小乐乐想要给自己搭建一个积木城堡。 积木城堡我们假设为n*m的平面矩形。 小乐乐现在手里有 1*2，2*1两种地砖。 小乐乐想知道自己有多少种组合方案。