动态规划

求解目标
- 最优化（最大或最小）
- 计数（一般需要取模，整数可能涉及到乘法逆元，实数可能涉及到概率）
转移方式
- 考虑哪些状态转移到自己（简单题，可以根据自己推断出之前的状态，容易进行进一步优化）
- 考虑自己转移到哪些状态（复杂题，无法根据自己推断出之前的状态，很难进行进一步优化）
状态表示
- 考虑起点到自己的最优解或方案数（一般情况）
- 考虑自己到终点的最优解或方案数（一些概率期望题）
动态规划时间复杂度，以下三部分乘积
- 状态数（数组开多大）
- 转移数（计算每个状态时需要用到多少个状态）
- 转移时间 (O(1))
动态规划要素
- 状态含义是什么（能回答最终的问题，任何一个状态可以由其他状态推出）
- 状态之间如何转移
- 状态初始化（边界条件）如何设置

经典题目

数字三角形

最长不下降子序列

定义
- 子序列 subsequence 可以不连续
- 子串 subarray 必须连续
四个相似的问题
- 最长不下降子序列 a[i] <= a[i+1]
- 最长上升子序列 a[i] < a[i+1]
- 最长不上升子序列 a[i] >= a[i+1]
  - 可以通过数组reverse 或者所有数字取相反数转化为最长不下降子序列
- 最长下降子序列 a[i] > a[i+1]
  - 可以通过数组reverse 或者所有数字取相反数转化为最长上升子序列
解法
- O(n^2) 直接动态规划，f[i] 表示 a[i] 结尾的最长不下降子序列的长度
- O(n log n) 二分搜索， f[i] 表示长度为i的最优解，最后一位最小是多少
- O(n log n) 数据结构， f[i] 表示最后一位为数值i的最优解，最后长是多少

最长公共子序列

定义
- 子序列 subsequence 可以不连续
- 子串 subarray 必须连续
- 最长公共子序列和最长公共子串是完全不一样的题目
- 两个排列的最长公共子序列可以转化为最长不下降子序列
编辑距离

线性状态动态规划

前缀的最优解
- 可能多维

P2758 编辑距离
P1279 字串距离

区间动态规划

状态是一个区间

O(n^3) f[i][j] = max(f[i][j], f[i][k] + f[k][j] + ....) P1063 能量项链
O(n^2) f[i][j] = max(f[i][j-1] + ..., f[i+1][j] + ....) P3205 [HNOI2010]合唱队
四边形不等式 P1880 [NOI1995]石子合并

树形动态规划

状态是一个子树
两次DFS的动态规划（求每个点的结果）
- 第一次求每个子树的答案，根节点的答案就是最终的答案
- 第二次把根节点的答案传到每个节点上
树上背包，有一种看上去是 $O(n^3)$ ，但实际上是 $O(n^2)$ 的动态规划 P1273 有线电视网

背包

常见错误贪心方法
- 优先选价值大的
- 优先选体积小的
- 优先选价值/体积比例大的
- 优先选价值-体积差值大的
求解目标
- 最优化
- 计数 / 只考虑方案数是否为0 / 只问方案数的奇偶性
最优化的特殊情况
- 是否要求用完所有体积
按每种物品的个数
- 零一背包
  - 分组背包
    - 同一组里的物品只能选1个
- 完全背包
- 混合背包
  - 最优化
    - 二进制拆分
    - 单调队列
  - 计数
    - 部分和优化
- 只考虑方案数是否为0的零一背包，可以用 bitset 优化 P2639 [USACO09OCT]Bessie's Weight Problem G
- 背包计数不考虑物品顺序，如果考虑需要交换循环的顺序
二维背包，有两维限制，限制体积和重量

有向无环图动态规划 DAG

拓扑排序
记忆化搜索
有的时候是一般的有向图，通过Tarjan强连通分量算法缩成有向无环图

状态压缩动态规划

子集
决策一个排列，直接暴力 n! * n, 动态规划 2^n * n^2  f[i(i 是一个集合)] -> f[i | (1 << j)]
决策一个排列，但是要记录最后一个是什么  f[i(i 是一个集合)][j] -> f[i | (1 << k)][k]
每一行的状态压缩成一个数字，两行之间暴力枚举，检查是否可以转移
插头动态规划，逐格转移

数位动态规划

前导0    P1590 失踪的7

int F(int n) # <n的答案，如果需要 <=n 的答案，调用F(n+1)
12345
0????
10???
11???
120??
121??
122??
1230?
1231?
1232?
1233?
12340
12341
12342
12343
12344

(2,3) (3,5) (5,10) (10,2) (2,3) (3,5) (5,10) (10,2)

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

https://www.luogu.com.cn/problem/P1216

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5

在上面的样例中,从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大

输入格式

第一个行一个正整数 $r$ ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】
对于 $100\%$ 的数据， $1\le r \le 1000$ ，所有输入在 $[0,100]$ 范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1020][1020];
int f[1020][1020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j <= i; j++) {
			f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
		}
	}
	printf("%d\n", f[0][0]);
	return 0;
}

题解

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

对于每个位置第i行第j列
记录 f[i][j] 起点到第i行第j列的最大值

状态的含义

从(1, 1)到(i, j)的最大值
从(i, j)到第n行的最大值

转移也有两种写法

自己在(i, j) 一定是从(i-1,j-1) 或 (i-1,j) 到自己
自己在(i, j) 下一步可以到(i+1,j) 或 (i+1,j+1)

贪心是错的
每次走较大的一边错误

动态规划 2种思路
从起点到 (i, j) 记录最优解 f[i][j]
f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]
7
10 15
18 16 15
20 25 20 19
24 30 27 26 24

从 (i, j) 到终点记录最优解 f[i][j]
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + a[i][j]
30
23 21
20 13 10
7 12 10 10
4 5 2 6 5

P2871 [USACO07DEC]Charm Bracelet S

https://www.luogu.com.cn/problem/P2871

题目描述

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$ ，价值是 $D_i$ 。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

第一行：物品个数 $N$ 和背包大小 $M$ 。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$ 。

输出格式

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

输出一行最大价值。

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, f[20020];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		for (int j = m; j >= x; j--) {
			f[j] = max(f[j], f[j - x] + y);
		}
	}
	printf("%d\n", f[m]);
	return 0;
}

题解

最优化零一背包
最优化 01背包

P2639 [USACO09OCT]Bessie's Weight Problem G

https://www.luogu.com.cn/problem/P2639

题目描述

Bessie像她的诸多姊妹一样，因为从Farmer John的草地吃了太多美味的草而长出了太多的赘肉。所以FJ将她置于一个及其严格的节食计划之中。她每天不能吃多过H (5 <= H <= 45,000)公斤的干草。 Bessie只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的N (1 <= N <= 500)捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。给定一个列表表示每捆干草的重量S_i (1 <= S_i <= H), 求Bessie不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。

输入格式

* 第一行: 两个由空格隔开的整数: H 和 N * 第2到第N+1行: 第i+1行是一个单独的整数，表示第i捆干草的重量S_i。

输出格式

* 第一行: 一个单独的整数表示Bessie在限制范围内最多可以吃多少公斤的干草。

样例 #1

样例输入 #1

样例输出 #1

提示

输入说明:

有四捆草，重量分别是15, 19, 20和21。Bessie在56公斤的限制范围内想要吃多少就可以吃多少。

输出说明:

Bessie可以吃3捆干草（重量分别为15, 20, 21）。恰好达到她的56公斤的限制。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x;
bitset<100000> f;
int main() {
	f[0] = true;
	scanf("%d%d", &m, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		f |= f << x;
	}
	for (int i = m; i >= 0; i--) {
		if (f[i]) {
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}

题解

只关注方案数是否为0的零一背包，可以用 bitset 优化

P5196 [USACO19JAN]Cow Poetry G

https://www.luogu.com.cn/problem/P5196

题目背景

USACO19年一月金组第一题

题目描述

不为Farmer John所知的是，Bessie还热衷于资助艺术创作！最近，她开始研究许多伟大的诗人们，而现在，她想要尝试创作一些属于自己的诗歌了。
Bessie认识N（1≤N≤5000）个单词，她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。

Bessie的每首诗由M行组成（1≤M≤10^5），每一行必须由K（1≤K≤5000）个音节构成。此外，Bessie的诗必须遵循某个指定的押韵模式。

Bessie想要知道她可以写出多少首符合限制条件的不同的诗。

输入格式

输入的第一行包含N、M和K。
以下N行，每行包含两个整数si（1≤si≤K）和ci（1≤ci≤N）。这表示Bessie认识一个长度（以音节为单位）为si、属于韵部ci的单词。

最后M行描述了Bessie想要的押韵模式，每行包含一个大写字母ei。所有押韵模式等于ei的行必须以同一韵部的单词结尾。不同ei值的行并非必须以不同的韵部的单词结尾。

输出格式

输出Bessie可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对1,000,000,007取余的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

在这个例子中，Bessie认识三个单词。前两个单词押韵，长度分别为三个音节和四个音节，最后一个单词长度为三个音节，不与其他单词押韵。她想要写一首三行的诗，每行包含十个音节，并且第一行和最后一行押韵。共有960首这样的诗。以下是一首满足要求的诗（其中1，2、3分别代表第一个、第二个、第三个单词）：121 123 321。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, l, p = 1000000007;
int f[5020];
int s[5020];
int c[5020];
int v[26];
int z[5020];
int pw(int x, int y) {
	int re = 1;
	for (; y > 0; y >>= 1) {
		if (y & 1) {
			re = (long long)re * x % p;
		}
		x = (long long)x * x % p;
	}
	return re;
}
int main() {
	scanf("%d%d%d", &n, &m, &l);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &s[i], &c[i]);
	}
	f[0] = 1;
	for (int i = 1; i <= l; i++) {
		for (int j = 0; j < n; j++) {
			if (i >= s[j]) {
				f[i] = (f[i] + f[i - s[j]]) % p;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		z[c[i]] = (z[c[i]] + f[l - s[i]]) % p;
	}
	for (int i = 0; i < m; i++) {
		char ch;
		scanf(" %c", &ch);
		v[ch - 'A']++;
	}
	int ans = 1;
	for (int i = 0; i < 26; i++) {
		if (v[i] == 0) {
			continue;
		}
		int tmp = 0;
		for (int j = 1; j <= n; j++) {
			tmp = (tmp + pw(z[j], v[i])) % p;
		}
		ans = (long long)ans * tmp % p;
	}
	printf("%d\n", ans);
	return 0;
}

题解

P6120 [USACO17JAN]Hoof, Paper, Scissor S

https://www.luogu.com.cn/problem/P6120

题目背景

本题与金组同名题目在题意上一致，唯一的差别在于对变手势次数的限制。

题目描述

你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。

“蹄子，剪刀，布”和“石头，剪刀，布”的规则十分类似，两只奶牛数到三，然后出一个代表蹄子，剪刀或布的手势。蹄子胜过剪刀，剪刀胜过布，布胜过蹄子。特别地，如果两只奶牛的手势相同，则视为平局。

现在 FJ 和 Bassie 要进行 $N$ 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换一次手势。

现在请你帮 Bassie 求出她最多能赢多少轮。

输入格式

第一行输入一个整数 $N$ （ $1 \leq N \leq 10^5$ ）。

接下来 $N$ 行，每行一个字母，代表 FJ 这一轮出的手势。H 代表蹄子（Hoof），S 代表剪刀（Scissors），P 代表布（Paper）。

输出格式

输出一个整数，代表 Bassie 在最多变换一次手势的前提下最多赢多少轮。

样例 #1

样例输入 #1

5
P
P
H
P
S

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m = 1;
char c;
int f[21][3];
int g[21][3];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf(" %c", &c);
		c = (c < 'P') + (c < 'S');
		memcpy(g, f, sizeof g); // g = f
		memset(f, 0, sizeof f); // f = 0
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				f[j][k] = g[j][k] + (c == k);
			}
			if (j > 0)
			{
				f[j][c] = max(f[j][c], max(g[j-1][0], max(g[j-1][1], g[j-1][2])) + 1);
			}
		}
	}
	printf("%d\n", max(f[m][0], max(f[m][1], f[m][2])));
	return 0;
}

题解

P3609 [USACO17JAN]Hoof, Paper, Scissor G

https://www.luogu.com.cn/problem/P3609

题目背景

本题与银组同名题目在题意上一致，唯一的差别在于对变手势次数的限制。

题目描述

你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。

现在 FJ 和 Bassie 要进行 $N$ 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换 $K$ 次手势。

现在请你帮 Bassie 求出她最多能赢多少轮。

输入格式

第一行输入两个整数 $N,K$ （ $1 \leq N \leq 10^5$ ， $0 \leq K \leq 20$ ）。

接下来 $N$ 行，每行一个字母，代表 FJ 这一轮出的手势。H 代表蹄子（Hoof），S 代表剪刀（Scissors），P 代表布（Paper）。

输出格式

输出一个整数，代表 Bassie 在最多变换 $K$ 次手势的前提下最多赢多少轮。

样例 #1

样例输入 #1

5 1
P
P
H
P
S

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
char c;
int f[21][3];
int g[21][3];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf(" %c", &c);
		c = (c < 'P') + (c < 'S');
		memcpy(g, f, sizeof g); // g = f
		memset(f, 0, sizeof f); // f = 0
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				f[j][k] = g[j][k] + (c == k);
			}
			if (j > 0)
			{
				f[j][c] = max(f[j][c], max(g[j-1][0], max(g[j-1][1], g[j-1][2])) + 1);
			}
		}
	}
	printf("%d\n", max(f[m][0], max(f[m][1], f[m][2])));
	return 0;
}

题解

P6120 [USACO17JAN]Hoof, Paper, Scissor S
P3609 [USACO17JAN]Hoof, Paper, Scissor G

不能
f[i][j] 前i轮，变换了j次，最多赢几局
这样做的话需要枚举最后一种手势，用了多少轮，时间复杂度O(n^2)太慢了

f[i][j][c]
前i轮，变换了j次，最后一轮出的c，最多平局几次

P5124 [USACO18DEC]Teamwork G

https://www.luogu.com.cn/problem/P5124

题目描述

在 Farmer John 最喜欢的节日里，他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而 Farmer John 即将得到这一教训。

Farmer John 的 $N$ 头奶牛（ $1\le N\le 10^4$ ）排成一行，方便起见依次编号为 $1\dots N$ 。奶牛 $i$ 的包装礼物的技能水平为 $s_i$ 。她们的技能水平可能参差不齐，所以 FJ 决定把她的奶牛们分成小组。每一组可以包含任意不超过 $K$ 头的连续的奶牛（ $1\le K\le 10^3$ ），并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。

请帮助 FJ 求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值。

输入格式

输入的第一行包含 $N$ 和 $K$ 。以下 $N$ 行按照 $N$ 头奶牛的排列顺序依次给出她们的技能水平。技能水平是一个不超过 $10^5$ 的正整数。

输出格式

输出 FJ 通过将连续的奶牛进行分组可以达到的最大技能水平和。

样例 #1

样例输入 #1

样例输出 #1

提示

在这个例子中，最优的方案是将前三头奶牛和后三头奶牛分别分为一组，中间的奶牛单独成为一组（注意一组的奶牛数量可以小于 $K$ ）。这样能够有效地将 $7$ 头奶牛的技能水平提高至 $15$ 、 $15$ 、 $15$ 、 $9$ 、 $10$ 、 $10$ 、 $10$ ，和为 $84$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10020];
int f[10020];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		int mx = a[i];
		for (int j = 1; j <= m && j <= i; j++) {
			f[i] = max(f[i], f[i - j] + mx * j);
			mx = max(mx, a[i - j]);
		}
	}
	cout << f[n] << endl;
	return 0;
}

题解

P5424 [USACO19OPEN]Snakes G

https://www.luogu.com.cn/problem/P5424

题目描述

传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。

Bessie装备了一个捕网，用来捕捉 $N$ 组排成一行的蛇（ $1 \leq N \leq 400$ ）。Bessie必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当Bessie抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。

一个大小为 $s$ 的捕网意味着Bessie可以抓住任意包含 $g$ 条的一组蛇，其中 $g \leq s$ 。然而，每当Bessie用大小为 $s$ 的捕网抓住了一组 $g$ 条蛇，就意味着浪费了 $s-g$ 的空间。Bessie可以任意设定捕网的初始大小，并且她可以改变 $K$ 次捕网大小（ $1 \leq K<N$ ）。

请告诉Bessie她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

输入格式

输入的第一行包含 $N$ 和 $K$ 。

第二行包含 $N$ 个整数 $a_1, \ldots ,a_N$ ，其中 $a_i$ （ $0 \leq a_i \leq 10^6$ ）为第 $i$ 组蛇的数量。

输出格式

输出一个整数，为Bessie抓住所有蛇的总浪费空间的最小值。

样例 #1

样例输入 #1

6 2
7 9 8 2 3 2

样例输出 #1

提示

Bessie可以设置她的捕网开始时大小为7。当她抓完第一组蛇之后，她将她的捕网的大小调整为9，保持这个大小直到抓完第4组蛇，再将捕网大小调整为3。总浪费空间为 $(7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
long long f[420][420];
long long a[420];
int n, m;
int main() {
	cin >> n >> m;
	m++;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	memset(f, 0x3f, sizeof f);
	f[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			long long sm = 0;
			long long mx = 0;
			for (int k = i - 1; k >= 0; k--) {
				sm += a[k];
				mx = max(mx, a[k]);
				f[i][j] = min(f[i][j], f[k][j - 1] + (mx * (i - k) - sm));
			}
		}
	}
	cout << f[n][m] << endl;
	return 0;
}

题解

记忆化搜索

图中没有环
最优子结构（如果希望最终的结果 mod 100最大呢？）
无后效性（如果要求路径上的中位数最大相当于到(i, j)只记录和不够）

最长不下降子序列 / 最长公共子序列

https://www.spoj.com/problems/HMLIS/
最长上升子序列的个数

P5156

https://www.luogu.com.cn/problem/P5156
为什么删去的是第k小的集合，剩下的一定是第k的集合
求字典序第k大的最长不下降子序列

3 2 1 6 5 4 9 8 7

求第13大的最长不下降子序列是什么？
以3开始的最长不下降子序列长度是多少？方案数多少？长度是3，方案数是9
方案数不够，13 -= 9 求剩下的中，第4大

以2开始的最长不下降子序列长度是多少？方案数多少？长度是3，方案数是9
方案数够了，求剩下的中，第4大

第一位是2
下一位是什么呢？

以6开始的最长不下降子序列长度是多少？方案数多少？长度是2，方案数是3
方案数不够，4 -= 3 求剩下的中，第1大

以5开始的最长不下降子序列长度是多少？方案数多少？长度是2，方案数是3
方案数够了，求剩下的中，第1大

第二位是5
下一位是什么呢？

以9开始的最长不下降子序列长度是多少？方案数多少？长度是1，方案数是1
方案数够了

第三位是9

每一个数字，如果可能出现在LIS中，那么他在LIS中的位置是唯一的

1 4 7 2 5 8 3 6 9

LIS长度是5
以自己为开始 LIS长度是5的哪些数字可能 1
以自己为开始 LIS长度是4的哪些数字可能 4 2
以自己为开始 LIS长度是3的哪些数字可能 7 5 3
以自己为开始 LIS长度是2的哪些数字可能 8 6
以自己为开始 LIS长度是1的哪些数字可能 9

每一位的可能性，都是降序的
比如在第二位选择了2，
那么第三位不可能选择7

8 8 7 7 9 9
1 2 3 4 5 6

4 3 2 1 6 5 排序之后

最长公共子序列 / 编辑距离 / ……

P6119 [USACO17FEB]Why Did the Cow Cross the Road II G

https://www.luogu.com.cn/problem/P6119

题目背景

本题与白金组同名题目在题意上一致，唯一的差别是数据范围。

题目描述

Farmer John 饲养了 $N$ 种奶牛，编号从 $1$ 到 $N$ 。一些品种的奶牛和其他奶牛间相处良好，事实证明，如果两个品种的奶牛编号分别为 $a,b$ ，当 $|a-b| \leq 4$ 时，这两个品种的奶牛能友好相处，否则不能友好相处。

一条长长的道路贯穿整个农场，道路的左侧有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场），道路的右侧也有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场）。为了让奶牛们安全穿过马路，Farmer John 希望能在马路上画出一些人行道（牛行道？），要求这些人行道满足如下条件：

人行道从左侧的某个牧场出发，连接到右侧的某个牧场；
人行道连接的两个牧场的奶牛要能友好相处；
人行道不能在道路中间相交；
每个牧场只能与一条人行道相连。

你需要帮 FJ 求出最多能有多少条人行道。

输入格式

输入第一行一个整数 $N$ （ $1 \leq N \leq 1000$ ）。

接下来 $N$ 行，每行一个整数 $a_i$ ，代表道路左侧第 $i$ 个牧场的奶牛品种编号。

接下来 $N$ 行，每行一个整数 $b_i$ ，代表道路右侧第 $i$ 个牧场的奶牛品种编号。

输出格式

输出最多能画多少条人行道。

样例 #1

样例输入 #1

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1020];
int b[1020];
int f[1020][1020];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (abs(a[i] - b[j]) <= 4)
			{
				f[i][j] = f[i - 1][j - 1] + 1;
			}
			else
			{
				f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			}
		}
	}
	printf("%d\n", f[n][n]);
	return 0;
}

题解

f[i][j] 表示第一个序列的前i个，和第二个序列的前j个，的最优解

P1279 字串距离

https://www.luogu.com.cn/problem/P1279

题目描述

设有字符串 $X$ ，我们称在 $X$ 的头尾及中间插入任意多个空格后构成的新字符串为 $X$ 的扩展串，如字符串 $X$ 为abcbcd，则字符串abcb□cd，□a□bcbcd□和abcb□cd□ 都是 $X$ 的扩展串，这里□代表空格字符。

如果 $A_1$ 是字符串 $A$ 的扩展串， $B_1$ 是字符串 $B$ 的扩展串， $A_1$ 与 $B_1$ 具有相同的长度，那么我们定义字符串 $A_1$ 与 $B_1$ 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为 $0$ 。在字符串 $A$ 、 $B$ 的所有扩展串中，必定存在两个等长的扩展串 $A_1$ ， $B_1$ ，使得 $A_1$ 与 $B_1$ 之间的距离达到最小，我们将这一距离定义为字符串 $A$ ， $B$ 的距离。

请你写一个程序，求出字符串 $A$ ， $B$ 的距离。

输入格式

输入文件第一行为字符串 $A$ ，第二行为字符串 $B$ 。 $A$ ， $B$ 均由小写字母组成且长度均不超过 $2000$ 。第三行为一个整数 $K(1\leq K\leq 100)$ ，表示空格与其他字符的距离。

输出格式

输出文件仅一行包含一个整数，表示所求得字符串 $A,B$ 的距离。

样例 #1

样例输入 #1

cmc
snmn
2

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
char a[2020], b[2020];
int f[2020][2020];
int n, m, k;
int main() {
	scanf("%s%s%d", a + 1, b + 1, &k);
	n = strlen(a + 1);
	m = strlen(b + 1);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == 0 || j == 0) {
				f[i][j] = (i + j) * k;
			} else {
				f[i][j] = min(f[i - 1][j - 1] + abs(a[i] - b[j]), min(f[i - 1][j], f[i][j - 1]) + k);
			}
		}
	}
	printf("%d\n", f[n][m]);
	return 0;
}

题解

f[i][j] 表示第一个序列的前i个，和第二个序列的前j个，的最优解

样例

 c mc 
s nm n

m和m对应了，有5个位置是字符匹配空格，总距离是5 * 2 = 10

f[i][j] 表示A串的前i个字符改成 B串的前j个字符的最小代价

The min cost to change A[1..i] to B[1..j]
f[i][j] = min(f[i-1][j-1] + abs(a[i] - b[j]), f[i][j-1] + K, f[i-1][j] + K)

https://www.luogu.com.cn/problem/P1115
P1115 最大子段和

f[i] 表示以 a[i] 结尾的最大子段和
f[i] = max(f[i-1], 0) + a[i]

P1181 数列分段Section I

P5124 [USACO18DEC]Teamwork G
f[i] best solution of the first i cows

for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}

for (int i = 1; i <= n; i++)
{
int mx = 0;
for (int j = i - 1; j >= i - k && j >= 0; j++) // last group [j, i-1] length i-j
{
mx = max(mx, a[j]);
f[i] = max(f[i], f[j] + (i-j) * mx);
}
}

P5424 [USACO19OPEN]Snakes G

区间动态规划
前缀

http://usaco.org/index.php?page=viewproblem2&cpid=897
USACO 2019 January Contest, Gold
Problem 1. Cow Poetry

http://usaco.org/index.php?page=viewproblem2&cpid=863
USACO 2018 December Contest, Gold
Problem 3. Teamwork

f[i] 前i个的最优解

状态数O(n)
转移数O(k)
转移时间O(1)

http://usaco.org/index.php?page=viewproblem2&cpid=945
USACO 2019 US Open Contest, Gold
Problem 1. Snakes

f[i][j] 前i个蛇，用了j个大小，最优解是什么

P6120 [USACO17JAN]Hoof, Paper, Scissor S

https://www.luogu.com.cn/problem/P6120

题目背景

本题与金组同名题目在题意上一致，唯一的差别在于对变手势次数的限制。

题目描述

你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。

现在 FJ 和 Bassie 要进行 $N$ 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换一次手势。

现在请你帮 Bassie 求出她最多能赢多少轮。

输入格式

第一行输入一个整数 $N$ （ $1 \leq N \leq 10^5$ ）。

接下来 $N$ 行，每行一个字母，代表 FJ 这一轮出的手势。H 代表蹄子（Hoof），S 代表剪刀（Scissors），P 代表布（Paper）。

输出格式

输出一个整数，代表 Bassie 在最多变换一次手势的前提下最多赢多少轮。

样例 #1

样例输入 #1

5
P
P
H
P
S

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m = 1;
char c;
int f[21][3];
int g[21][3];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf(" %c", &c);
		c = (c < 'P') + (c < 'S');
		memcpy(g, f, sizeof g); // g = f
		memset(f, 0, sizeof f); // f = 0
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				f[j][k] = g[j][k] + (c == k);
			}
			if (j > 0)
			{
				f[j][c] = max(f[j][c], max(g[j-1][0], max(g[j-1][1], g[j-1][2])) + 1);
			}
		}
	}
	printf("%d\n", max(f[m][0], max(f[m][1], f[m][2])));
	return 0;
}

题解

P3609 [USACO17JAN]Hoof, Paper, Scissor G

https://www.luogu.com.cn/problem/P3609

题目背景

本题与银组同名题目在题意上一致，唯一的差别在于对变手势次数的限制。

题目描述

你可能玩过“石头，剪刀，布”，这个游戏在奶牛中同样流行，不过它的名字变成了“蹄子，剪刀，布”。

现在 FJ 和 Bassie 要进行 $N$ 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒，她最多只想变换 $K$ 次手势。

现在请你帮 Bassie 求出她最多能赢多少轮。

输入格式

第一行输入两个整数 $N,K$ （ $1 \leq N \leq 10^5$ ， $0 \leq K \leq 20$ ）。

接下来 $N$ 行，每行一个字母，代表 FJ 这一轮出的手势。H 代表蹄子（Hoof），S 代表剪刀（Scissors），P 代表布（Paper）。

输出格式

输出一个整数，代表 Bassie 在最多变换 $K$ 次手势的前提下最多赢多少轮。

样例 #1

样例输入 #1

5 1
P
P
H
P
S

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
char c;
int f[21][3];
int g[21][3];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf(" %c", &c);
		c = (c < 'P') + (c < 'S');
		memcpy(g, f, sizeof g); // g = f
		memset(f, 0, sizeof f); // f = 0
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				f[j][k] = g[j][k] + (c == k);
			}
			if (j > 0)
			{
				f[j][c] = max(f[j][c], max(g[j-1][0], max(g[j-1][1], g[j-1][2])) + 1);
			}
		}
	}
	printf("%d\n", max(f[m][0], max(f[m][1], f[m][2])));
	return 0;
}

题解

P6120 [USACO17JAN]Hoof, Paper, Scissor S
P3609 [USACO17JAN]Hoof, Paper, Scissor G

不能
f[i][j] 前i轮，变换了j次，最多赢几局
这样做的话需要枚举最后一种手势，用了多少轮，时间复杂度O(n^2)太慢了

f[i][j][c]
前i轮，变换了j次，最后一轮出的c，最多平局几次

动态规划更新时有2种写法

考虑哪些状态可以转移到自己
考虑自己可以转移到哪些状态

动态规划有2种写法

递推
一般用递推写
递归（记忆化搜索）
有的题目不容易决定动态规划的顺序

https://www.luogu.com.cn/problem/P3146
https://www.luogu.com.cn/problem/P3147
如果起点i确定，凑出的值确定，终点位置是确定的

2 2 2 4

树形动态规划
状态一般是子树怎么怎么样

http://usaco.org/index.php?page=viewproblem2&cpid=897
USACO 2019 January Contest, Gold
Problem 1. Cow Poetry

http://usaco.org/index.php?page=viewproblem2&cpid=863
USACO 2018 December Contest, Gold
Problem 3. Teamwork

http://usaco.org/index.php?page=viewproblem2&cpid=945
USACO 2019 US Open Contest, Gold
Problem 1. Snakes

f[i][j]
First i integers, used j different sizes
minimize the wasted space.

consider the range of last size
a[k+1], a[k+2], …, a[i]
f[i][j] = min(f[i][j], f[k][j – 1] + (mx[k + 1][i] * (i – k) – (s[i] – s[k])));
First k integers, used j-1 different sizes + the wasted space of (a[k+1], a[k+2], …, a[i])

the number of states * the number of transitions * the time of a transition

mx[i][j] = max(mx[i][j - 1], a[j]);
max(a[i], a[i+1], ..., a[j-1], a[j]) = max(max(a[i], a[i+1], ..., a[j-1]), a[j])

http://usaco.org/index.php?page=viewproblem2&cpid=791
USACO 2018 January Contest, Gold
Problem 3. Stamp Painting

Find the total number of plans
Find the number of invalid plans

Knapsack

01 knapsack problem
unbounded knapsack problem
optimize / maximize
counting

P2925 [USACO08DEC]Hay For Sale S

https://www.luogu.com.cn/problem/P2925

题目描述

Farmer John suffered a terrible loss when giant Australian cockroaches ate the entirety of his hay inventory, leaving him with nothing to feed the cows. He hitched up his wagon with capacity C (1 <= C <= 50,000) cubic units and sauntered over to Farmer Don's to get some hay before the cows miss a meal.

Farmer Don had a wide variety of H (1 <= H <= 5,000) hay bales for sale, each with its own volume (1 <= V_i <= C). Bales of hay, you know, are somewhat flexible and can be jammed into the oddest of spaces in a wagon.

FJ carefully evaluates the volumes so that he can figure out the largest amount of hay he can purchase for his cows.

Given the volume constraint and a list of bales to buy, what is the greatest volume of hay FJ can purchase? He can't purchase partial bales, of course. Each input line (after the first) lists a single bale FJ can buy.

约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草．顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，

他最多可以运回多少体积的干草呢？

输入格式

* Line 1: Two space-separated integers: C and H

* Lines 2..H+1: Each line describes the volume of a single bale: V_i

输出格式

* Line 1: A single integer which is the greatest volume of hay FJ can purchase given the list of bales for sale and constraints.

样例 #1

样例输入 #1

样例输出 #1

提示

The wagon holds 7 volumetric units; three bales are offered for sale with volumes of 2, 6, and 5 units, respectively.

Buying the two smaller bales fills the wagon.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x;
bitset<50020> f;
int main() {
	scanf("%d%d", &m, &n);
	f[0] = 1;
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		f |= f << x;
	}
	for (int i = m; i >= 0; i--) {
		if (f[i]) {
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}

题解

https://www.luogu.com.cn/problem/P2925
01 Knapsack problem
Bessie's Weight Problem

include <bits/stdc++.h>

using namespace std;
int n, m, x;
bitset<50020> f;
int main() {
scanf("%d%d", &m, &n);
f[0] = 1;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
f |= f << x;
// f[x+0] |= f[0]
// f[x+1] |= f[1]
// f[x+2] |= f[2]
...
// f[m] |= f[m-x]
}
for (int i = m; i >= 0; i--) {
// find the largest i, such that f[i] == 1 && i <= m
if (f[i]) {
printf("%d\n", i);
break;
}
}
return 0;
}

include <bits/stdc++.h>

using namespace std;
int n, m, x;
int f[50020];
int main() {
scanf("%d%d", &m, &n);
f[0] = 1;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
for (int j = m; j >= x; j--)
{
f[j] |= f[j - x];
}
}
for (int i = m; i >= 0; i--) {
// find the largest i, such that f[i] == 1 && i <= m
if (f[i]) {
printf("%d\n", i);
break;
}
}
return 0;
}

http://usaco.org/index.php?page=viewproblem2&cpid=839
USACO 2018 US Open Contest, Gold
Problem 3. Talent Show

f[i] the total weight is i, what is the maximum talent.
TLE their total weight is very large.

f[i] the total talent is i, what is the minimum weight.
WA for some total talent, if we choose the minimum weight, it is < w

Binary search the ratio, for each cow, it has a new value t[i] - r * w[i]
we want to find a subset
total weight >= W
total new value >= 0
now we can do DP on weight.

O(W * n)

Binary Search

integer
real numbers / control the number of times.

1
2
3
4
5
6

6
5
4
3
2
1

a[i] the position of i in the first sequence
b[i] the position of i in the second sequence

if abs(i - j) <= 4:
add new point(a[i], b[j])

P4084 [USACO17DEC]Barn Painting G

http://usaco.org/current/data/sol_hps_gold_jan17.html

spoj REDRONESIA

f[i][j] length i, first j chars, the number of words

f[i][j + 1] += f[i][j]
f[i + 1][j + 1] += f[i][j]
f[i + 2][j + 1] += f[i][j]

spoj ADACON

spoj TPGA

spoj SWAPDIFF1

3 4 6 5 1 2
2 4 6 5 1 3

5 6 1 2 4 3
5 1 6 2 4 3

xi > 0
x1 + x2 + ... + xk = n
the number of solutions is C(n-1, k-1)

xi >= 0
(x1 + 1) + (x2 + 1) + ... + (xk + 1) = n + k
the number of solutions is C(n+k-1, k-1)

xi > ai
(x1 - a1) + (x2 - a2) + ... + (xk - ak) = n - (a1 + a2 + ... + ak)
the number of solutions is C(n - (a1 + a2 + ... + ak), k-1)

2 >= xi >= 0
x1 + x2 + ... + xk = n
the number of solutions is C(n+k-1, k-1)

b1 >= x1 > 0
b2 >= x2 > 0
b3 >= x3 > 0

x1 + x2 + x3 = n
the number of solutions

C(n - 1, k - 1)

C(n - b1 - 1, k - 1)
C(n - b2 - 1, k - 1)
C(n - b3 - 1, k - 1)

C(n - b1 - b2 - 1, k - 1)
C(n - b1 - b3 - 1, k - 1)
C(n - b2 - b3 - 1, k - 1)

C(n - b1 - b2 - b3 - 1, k - 1)

if the first part < 0, it is 0

(1)
x1 > 0
x2 > 0
x3 > 0

(2)
x1 > b1
x2 > 0
x3 > 0

(3)
x1 > 0
x2 > b2
x3 > 0

[] - [b1] - [b2] - [b3] + [b1, b2] + [b1, b3] + [b2, b3] - [b1, b2, b3]

CF1238E Keyboard Purchase
bitmasks/dp

f[i]
the first several chars are set i

#include<bits/stdc++.h>
using namespace std;const int N=(1<<21)+3;
int dp[N],g[20][20],c,n,m,i,j,k;char s[N];
int main(){
    for(scanf("%d%d%s",&n,&m,s+1),i=2;i<=n;++i)g[s[i]-'a'][s[i-1]-'a']=++g[s[i-1]-'a'][s[i]-'a'];
    // read the string
    // g['a']['b'] means the number of times, 'a' is next to 'b'

    for(i=1;i<(1<<m);++i)
    {
        dp[i]=2e9;
        for(j=c=0;j<m;++j)
            for(k=j+1;k<m;++k)
                if((i>>j&1)^(i>>k&1))
                    // for every pair of char
                    // if j and k are at different sides
                    c+=g[j][k];
        for(j=0;j<m;++j)
            if(i>>j&1)
                dp[i]=min(dp[i],dp[i^(1<<j)]+c);
        for(j=0;j<m;++j)
            if(~i>>j&1)
                dp[i|1<<j]=min(dp[i|1<<j],dp[i]+c);
    }printf("%d\n",dp[(1<<m)-1]);
}

CF11D A Simple Task
bitmasks/dp
start at the smallest vertex

f[i][j]
start from the lowbit of i, pass the set i, end at j, the number of plans

if lowbit of i, is connected with j, add f[i][j] to the answer

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int

using namespace std;

int n,m,t,u,v;
bool a[19][19]; //存边
ll ans,f[600001][19]; //状压

inline int qr(){ //快读
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    int res=ch^48;
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+(ch^48);
    return res;
}

int main(){
    n=qr(),m=qr();t=1<<n;
    for(rg i=1;i<=m;++i){
        u=qr()-1;v=qr()-1;
        a[u][v]=a[v][u]=1;//加边
    }
    for(rg i=0;i<n;++i)
        f[1<<i][i]=1; //初始化（创建以i为起点的路径）
    for(rg i=0;i<t;++i){
        // i is a vertex set
        for(rg j=0;j<n;++j){
            if(!f[i][j])continue; //加速
            // j is the last vertex of the path
            // j should be in i
            for(rg k=0;k<n;++k){
                if(!a[j][k])continue; //加速
                // k should not be in i
                // from j to k
                if((i&-i)>1<<k)continue; //起点不能改！！！（去重）
                // k can't be less than the start point
                if(1<<k&i)
                { //这个点走过
                    if((1<<k)==(i&-i)) //起点与终点相同
                    {
                        if k is the start point of the path
                        from lowbit(i) to j to k is a cycle.
                        ans+=f[i][j];
                    }
                }
                else
                {
                    f[i|1<<k][k]+=f[i][j]; //没走过就走！
                }
            }
        }
    }printf("%lld",(ans-m)/2); //处理之后再输出！
    // ignore the same edge twice
    // devided by two.
    return 0;
}

http://poj.org/problem?id=2411
another famous problem

https://www.luogu.com.cn/problem/P4799
https://ceoi2015.fi.muni.cz/day2/eng/day2task1-eng.pdf
split-half search
find all subsets of the first half
2 ** (n/2)

find all subsets of the second half
2 ** (n/2)

do two-pointer

we can not
for (int i = 1; i < 1 << n; i++)
{
for (int j = 0; j < n; j++)
{
if (i >> j & 1)
{
s[i] += a[j];
}
}
}

0100011110111000
0100011110110000
0000000000001000

http://www.usaco.org/index.php?page=viewproblem2&cpid=647
USACO 2016 US Open Contest, Gold
Problem 3. 248
f[i][j]

merge a[i] ... a[j] into 1 number
the largest result

1 1 1 1 3 2 2 -> 4
2 + 2 + 2 + 2 + 8 + 4 + 4 = 16

2 1 2 -> -1

this is wrong:
for (left end point)
for (right end point)
[1, 1]
[1, 2]
[2, 2]

for (length of interval)
for (start point)

import java.io.;
import java.util.;
public class two48 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("248.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("248.out")));
int n = Integer.parseInt(br.readLine());
int[] list = new int[n];
for(int i = 0; i < n; i++) {
list[i] = Integer.parseInt(br.readLine());
}
int[][] dp = new int[n][n];
int ret = 0;
for(int len = 1; len <= n; len++) {
for(int i = 0; i + len <= n; i++) {
int j = i+len-1;
dp[i][j] = -1;
if(len == 1) {
dp[i][j] = list[i];
}
for(int k = i; k < j; k++) {
if(dp[i][k] == dp[k+1][j] && dp[i][k] > 0) {
dp[i][j] = dp[i][k] + 1;
}
}
ret = Math.max(ret, dp[i][j]);
}
}
pw.println(ret);
pw.close();
}
}

http://www.usaco.org/index.php?page=viewproblem2&cpid=648
USACO 2016 US Open Contest, Platinum
Problem 1. 262144

f[i][j]
start from i
merge [i, f[i][j]) to a single number j
if no solution, f[i][j] = -1

if we can merge [i, f[i][j-1]) to j-1 and
merge [f[i][j-1], f[f[i][j-1]][j-1]) to j-1 then
f[i][j] = f[f[i][j-1]][j-1]

http://usaco.org/index.php?page=viewproblem2&cpid=574
USACO 2015 December Contest, Gold
Problem 2. Fruit Feast

#include <bits/stdc++.h>
using namespace std;
bool f[1000100]={1};//由于题目只需要判断可否达到饱食度，故不需要开int类型
int a,b,t;
int main(){
    cin>>t>>a>>b;
    for(int i=0;i<=t;++i)
    {
        f[i + a] |= f[i];
        f[i + b] |= f[i];
    }
    for(int i=b;i<=t;++i)f[i]|=f[i-b];
    for(int i=1;i<=t;++i)f[i/2]|=f[i];// if we can reach i, then we can reach i/2
    for(int i=0;i<=t;++i)
    {
        f[i + a] |= f[i];
        f[i + b] |= f[i];
    }
    while(!f[t])--t;//从饱食度最高值向低枚举
    cout<<t<<endl;
    return 0;
}

CF467C George and Job
f[i][j]
choose j intervals in the first i elements
if we don't choose a[i]
f[i][j] = max(f[i-1][j])
if we choose a[i-k+1] .. a[i]
f[i][j] = max(f[i-k][j-1] + sum(a[i-k+1] .. a[i]))

CF706C Hard problem
lexicographical

if A is a prefix of B
the shorter is smaller.

find the first different character
the smaller character is the smaller word.

s[i] the original string i
t[i] the reversed string i

f[i][0] if we don't reverse the i-th string, what is the min cost
f[i][1] if we do reverse the i-th string, what is the min cost

f[i][0] = min(f[i][0], f[i-1][0]) iff s[i] >= s[i-1]
f[i][0] = min(f[i][0], f[i-1][1]) iff s[i] >= t[i-1]
f[i][1] = min(f[i][1], f[i-1][0] + c[i]) iff t[i] >= s[i-1]
f[i][1] = min(f[i][1], f[i-1][1] + c[i]) iff t[i] >= t[i-1]

f[i][1] = min(f[i][1], f[i-1][])

https://codeforces.com/problemsets/acmsguru/problem/99999/347
sort them directly

b
ba

bba
bab

bc
b

bbc
bcb

bool cmp(string a, string b)
{
return a + b < b + a;
}

http://main.edu.pl/en/archive/oi/19/okr
https://www.acmicpc.net/problem/8228

abcabc = abc
bcabc = bcabc

the answer must be a divisor of the length of interval.
preprocess all prime divisors of each number.

Each query is a pair of integers a and b (1 ≤ a ≤ b ≤ n),

l = the length of interval
z = the answer

b - a + 1 == l
s[a .. b]

for the answer z
it must satisfy
s[a .. b-z] == s[a+z .. b]

abcabcabcabc == s
abcabcabc == s[a+z .. b]
abcabcabc == s[a .. b-z]

for some integer t
if it satisfies
s[a .. b-t] == s[a+t .. b]
then z is a divisor of t

'abcdef'

'a'
'a' * 100 + 'b'
'a' * 10000 + 'b' * 100 + 'c'
'a' * 1000000 + 'b' * 10000 + 'c' * 100 + 'd'
'a' * 100000000 + 'b' * 1000000 + 'c' * 10000 + 'd' * 100 + 'e'
'a' * 10000000000 + 'b' * 100000000 + 'c' * 1000000 + 'd' * 10000 + 'e' * 100 + 'f'

('a' * 10000000000 + 'b' * 100000000 + 'c' * 1000000 + 'd' * 10000 + 'e' * 100 + 'f') -
('a' * 10000 + 'b' * 100 + 'c') * 1000000 = ('d' * 10000 + 'e' * 100 + 'f')

for(int i = 1;i <= n;i++)
{
    ss[i] = ss[i-1]*seed;
}

Hash:
the same strings must have the same hash values.
the different strings should have different hash values.

https://codeforces.com/topic/60786/en3

http://www.lydsy.com/JudgeOnline/problem.php?id=3097
http://www.lydsy.com/JudgeOnline/problem.php?id=3098

by Sieve, we can get primes <= n
and the least prime factor of each number.

CF611C New Year and Domino

aaa.#a.#
.#aaaaa.

.#aaa.

a.#.##

aaaaaaa.

b.bb#bb#
.#b.bbbb

b#.b..

bb#b##

........

CF711C Coloring Trees

1 1 2 -> 1 + 3 + 6 = 10
2 1 1 -> 2 + 3 + 5 = 10

f[i][j][k]
O(n * k * m * m)

first i elements
j segments
the last color is k

CF835C Star sky

CF1215B The Number of Products
5 -3 3 -1 1
1 1 -1 -1 1 1

choose a prefix product 1
choose a prefix product -1
they form an interval whose product is negative.

s[r] = a[1] * a[2] * ... * a[r]
s[l] = a[1] * a[2] * ... * a[l]

if s[r] == -1 and s[l] == 1

a[l+1] * a[l+2] * ... * a[r] = s[r] / s[l] = -1

n * (n + 1) / 2

CF1207C Gas Pipeline

f[i][0] .... (i, 1) not include the pillar from (i, 0) to (i, 1)
f[i][1] .... (i, 2) not include the pillar from (i, 0) to (i, 2)

CF1239A Ivan the Fool and the Probability Theory

CF1221D Make The Fence Great Again

#include<bits/stdc++.h>
#define REP(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
char s[maxn];
ll f[maxn][2];
int n,a,b;
int main(){
    int T; cin>>T;
    while(T--){
        memset(f,0x3f,sizeof f);
        cin>>n>>a>>b;
        // a pipe
        // b pillar
        scanf("%s",s+1);
        f[0][0]=0;
        REP(i,1,n){
            if(s[i]=='0')
            {
                f[i][0]=min(f[i-1][0]+a+b,f[i-1][1]+a*2+b*2);
                f[i][1]=min(f[i-1][0]+a*2+b,f[i-1][1]+a+b*2);
            }
            else
            {
                f[i][1]=f[i-1][1]+a+b*2;
            }
        }
        cout<<f[n][0]+b<<'\n';
    }
    return 0;
}

CF1202B You Are Given a Decimal String...

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
3 3 3 1 1 4 2 2 2 3
2 2 2 0 0 3 1 1 1 2
[0][1][2][3][4][5][6][7][8][9] d

d[8] * 1 + d[6] * 2 = 3

0 5
0 -1 -1 -1 -1 0 -1 -1 -1 -1

from collections import*
s=input()
c=Counter((ord(y)-ord(x))%10 for x,y in zip(s,s[1:]))
for i in range(100):
    # (i//10) (i%10) counter
    a = [-1] * 10
    for j in range(1, 11):
        for k in range(j+1):
            x = ((j - k) * (i//10) + k * (i%10)) % 10
            if a[x] == -1:
                a[x] = j-1
    z = 0
    for x in c:
        if a[x] == -1:
            z = -1
            break
        else:
            z += a[x] * c[x]
    print(z)

CF1197D Yet Another Subarray Problem

#include <bits/stdc++.h>
using namespace std;
int n, m, l;
int a[300020];
int main()
{
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    long long z = 0;
    // best interval [l, r]
    for (int i = 0; i < m; i++)
    {
        // i == l % m

        long long s = 0;
        // here the interval is [l, r)
        for (int j = i; j < n; j++)
        {
            if (j % m == i)
            {
                s = max(s, 0LL) - K;
                // if s < 0, then delete the first (j - i) elements
                // from t*m to t*m+1
                // we need decrease K more
            }
            s += a[j]
            // [i, j] == [l, r];
            z = max(z, s);
        }
    }
    printf("%lld\n", z);
    return 0;
}

https://www.luogu.com.cn/problem/P1115

include <bits/stdc++.h>

using namespace std;
int n, x, s, z;
int main() {
scanf("%d", &n);
z = -10000;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
s = max(s, 0) + x;
// if we can choose empty subarray
// s = max(s + x, 0);
z = max(z, s);
}
printf("%d\n", z);
return 0;
}

CF1181C Flag

CF1155D Beautiful Array

CF1209E1 Rotate Columns (easy version)

CF1201D Treasure Hunting

CF1152D Neko and Aki's Prank
Catalan Number

sum(f[i][j] if (i+j) %2 == 1)

1 1
1 2 2
1 3 5 5

0 0
0 1 1
0 1 2 2

0 0
0 0 0
1 1 1 1

0 0
0 0 0
0 0 1 1

1
1 1
1 2 2
1 3 5 5

0
0 1
0 1 1
0 1 2 2

0
0 0
0 0 1
0 0 1 1

1
1 2
1 3 4
1 4 8 8

P5204 [USACO19JAN]Train Tracking 2 P

P5422 [USACO19OPEN]Compound Escape P

P6275 [USACO20OPEN]Sprinklers 2: Return of the Alfalfa P

P6277 [USACO20OPEN]Circus P

https://atcoder.jp/contests/cf17-relay-open/tasks
https://atcoder.jp/contests/code-festival-2017-quala
https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_d
|x1 - x2| + |y1 - y2|

(a1, b1)
a1 = x1 + y1
b1 = x1 - y1

(a2, b2)
a2 = x2 + y2
b2 = x2 - y2

|x1 - x2| + |y1 - y2| = max(|a1 - a2|, |b1 - b2|)

|d| = max(d, -d)

for two squares, if (ai - aj) == d, color them with different colors.
for two squares, if (bi - bj) == d, color them with different colors.

for two squares, if a / d, color them with different colors.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, d;
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x = (m + i + j) / d % 2;
            int y = (m + i - j) / d % 2;
            char c = "RGBY"[2 * x + y];
            printf("%c", c);
        }
        printf("\n");
    }
    return 0;
}

if (i1, j1) and (i2, j2), their distance is d
a1 = i1 + j1
b1 = i1 - j1
a2 = i2 + j2
b2 = i2 - j2
either abs(a1 - a2) == d || abs(b1 - b2) == d

abs(a1 - a2) == d
a1 / d % 2 is different from a2 / d % 2

https://atcoder.jp/contests/code-festival-2017-qualb

https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_e

Remove some red balls
Remove one blue ball, to do this, we set s, for the following B-1 balls, it can be either blue or red.
i is the number of blue balls removed in step 2
Remove some red balls
Remove one blue ball, to do this, we set t, for the following B-i-1 balls, it can be either blue or red.
j is the number of blue balls removed in step 4
Remove the remaining balls (some red + some blue)

special case:
remove all blue balls together.
there are R+1 ways

include <bits/stdc++.h>

using namespace std;
int n, m, p = 1000000007;
long long v[100020];
long long f[100020];
long long ans;
long long C(int n, int m) {
return f[n] * v[m] % p * v[n - m] % p;
}
int main() {
v[0] = v[1] = f[0] = f[1] = 1;
for (int i = 2; i <= 100010; i++) {
v[i] = v[p % i] * (p - p / i) % p;
}
for (int i = 2; i <= 100010; i++) {
f[i] = f[i - 1] * i % p;
v[i] = v[i - 1] * v[i] % p;
}
scanf("%d%d", &n, &m);
n = the number of red
m = the number of blue
ans = n + 1;
for (int i = 1; i < m; i++) {
if (m - i > n) {
continue;
}
for (int j = 1; j <= m - i; j++) {
if ((m - i) + (m - i - j) > n) {
continue;
}
ans += C(m - 1, i - 1) * C(m - i - 1, j - 1) % p * C(n - (m - i) - (m - i - j) + 2, 2) % p;
// i-1 balls of m-1 balls are blue
// j-1 balls of m-i-1 balls are blue
// the number of remaining red balls n - (m - i) - (m - i - j)
// distribute them in to step 1 3 5
ans %= p;
}
}
cout << ans << endl;
return 0;
}

https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_f
a a b b c c
a ac b b c
ac ac b b
ac acb b
acb acb
acbacb

a a a a a a a a b c

aaaabaaaac
aaaaacaaab
aaaaaaaabc

https://atcoder.jp/contests/code-festival-2017-qualc

spoj ISELECT

https://www.spoj.com/problems/ISELECT/