本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640975.html

cf1110e

给定一个序列 A{}，每次可以选择 1 < i < N 的一个元素，更新 $A_i = A_{i-1} + A_{i+1} - A_i$ 。
问是否可以是序列 A{} 变化得到序列 B{}。

判断差分、首项是否相等即可。

poj1191

题面

对于式子中一些没影响的东西去掉，原式就是求 $\sum n^2 a^2-n(\sum a_j)^2$

设 $dp(x_1, y_1, x_2, y_2, k)$ 为左上角为 $(x_1, y_1)$ ，右下角为 $(x_2,y_2)$ ，分成 $k$ 块平均和的最小值。

hdu7015

给定一个串 $S$ ，对于每一个前缀 $A$ 以及对应的后缀 $B$ ，问有多少个子串对之间的距离不超过 K。
两个相同长度的串的距离定义为他们不同字符的个数。

len <= 3000, K <= 3000

设 $len(i, j)$ 表示从 $i$ 和 $j$ 开始的子串距离不超过 $k$ 时的最长子串。

可以从 $len(i+1, j+1)$ 用均摊 $O(1)$ 的方法推出。

然后有四种转态：(设 $k$ 为划分的地方)

A： $i>k$ ，贡献为0
B: $i+len(i,j)-1>k$ , $k$ 每次右移贡献+1.
C: $i+len(i,j)-1<k$ ，贡献不变
D: $k>j$ ，贡献为0

hdu5550

计划建设 N 层高的运动楼，每层楼要么建游泳池，要么建乒乓球室，只能二选一。
已知第 i 层有 $T_i$ 个人打乒乓球， $P_i$ 个人想游泳。
如果该层楼没有对应的功能室，对应的人只能去最近的楼层运动。
单个人爬一层楼的额外运动量是 1，问最合理的设计下，满足每个人的需求时，最少付出的额外运动量总和是多少。

$N <= 4000,\ 0 <= T_i,P_i <= 10^{9}$

设 $dp(i,0/1,j)$ 表示第 $i$ 层建乒乓球/游泳池，且前一个和它不一样的楼层为 $j$ 的最小代价。

然后枚举 $j$ 是否等于 $i-1$ 进行转移。

hdu5794

问 $N * M$ 的矩阵，从左上角到右下角的方案数。
其中：

相邻两次的步长必须满足： $(y_2 - y_1)^2 + (x_2 - x_1)^2 = 5\ \&\&\ y2 > y1\ \&\&\ x2 > x1$ ；
有 $K$ 个格子不能进入。

$N,M <= 10^{9},\ K<=100$

条件1可以转化为每次向下或向右，用卢卡斯优化。

设 $f(i)$ 表示到第 $i$ 个关键点的方案数。

uvalive3363

题面描述了一个压缩串的规则，举例理解:

nowletsgogogoletsgogogo 可以压缩成 now2(lets3(go))；
nowletsgogogoletsgogogoandrunrunrun 可以压缩成 now2(lets3(go))and3(run)。

问给定某个原串，压缩后最短长度是多少。

len <= 200

区间dp。

uvalive-4490

书架上有 N 本书，书本高度是 [25cm，32cm]，凌乱地排着。
定义一排书的整齐度是指最少可以被划分成高度连续相等的书的段数。
比如 {30，32，32，31} 整齐度是 3。
比如 {31，32，31，32，31} 整齐度是 5。
现在最多从其中拿出 K 本书，然后塞回去。
问整理后，最少可以有多少段高度相等的连续区间。