区间DP

区间DP是一类比较简单的DP，因为DP状态一定是一个区间

时间复杂度

O(n2)O(n^2)

每次在原区间左侧或右侧增加一个元素
f[i][j] = min(f[i][j-1] + 和j有关的东西, f[i+1][j] + 和i有关的东西)
有时一个数组不够，还需要额外记录最终停在左边还是右边

O(n3)O(n^3)

新区间由两个小区间合并得到
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + 和i,k,j有关的东西)

循环顺序

区间DP有三种循环顺序
核心思想是 要保证 计算[i, j]时，所有被[i, j]包含的区间都已经计算了
动态规划表示状态时，要想清楚是闭区间，还是左闭右开（左右端点都包括，还是只包括左端点，不包括右端点）

枚举区间长度 l 从小到大 
    枚举起点 i (任意顺序)
        计算区间终点 j = i + l - 1
        for (int k = i; k < j; k++) 枚举所有转移方式
        {
            f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + 合并之后第i堆到第j堆的大小s[j]-s[i-1] )
        }
1 1
2 2
3 3
1 2
2 3
1 3

枚举起点 i 从大到小
    枚举终点 j 从小到大
3 3
2 2
2 3
1 1
1 2
1 3

枚举终点 j 从小到大
    枚举起点 i 从大到小
1 1
2 2
1 2
3 3
2 3
1 3

四边形不等式

相关题目

P1880 [NOI1995] 石子合并

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

题目描述

在一个圆形操场的四周摆放 NN 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 NN 堆石子合并成 11 堆的最小得分和最大得分。

输入格式

数据的第 11 行是正整数 NN，表示有 NN 堆石子。

第 22 行有 NN 个整数，第 ii 个整数 aia_i 表示第 ii 堆石子的个数。

输出格式

输出共 22 行，第 11 行为最小得分，第 22 行为最大得分。

样例 #1

样例输入 #1
4
4 5 9 4
样例输出 #1
43
54

提示

1≤N≤1001\leq N\leq 100，0≤ai≤200\leq a_i\leq 20。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[220], s[220];
int f[220][220];
int g[220][220];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i + n] = a[i];
	}
	for (int i = 1; i <= 2 * n; i++) {
		s[i] = s[i - 1] + a[i];
	}
	for (int l = 2; l <= n; l++) {
		for (int i = 1; i + l - 1 <= 2 * n; i++) {
			int j = i + l - 1;
			f[i][j] = 1e9;
			g[i][j] = 0;
			for (int k = i; k < j; k++) {
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
				g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
			}
		}
	}
	int ans1 = 1e9;
	int ans2 = 0;
	for (int i = 1; i <= n; i++) {
		ans1 = min(ans1, f[i][i + n - 1]);
		ans2 = max(ans2, g[i][i + n - 1]);
	}
	cout << ans1 << endl << ans2 << endl;
}

题解

环形，把数组重复两次

4 5 9 4 4 5 9 4

对于每个长度为n的区间都求最优解，再枚举区间起点即可

f[i][j] 从 第 i 堆 合并到 第 j 堆 最大/最小 得分
转移最后一次是怎么合并的假设是 [i,k] 合并 [k+1,j]

for (int k = i; k < j; k++)
{
    f[i][j] = max/min(f[i][j], f[i][k] + f[k+1][j] + a[i]+a[i+1]+...+a[j])
    f[i][j] = max/min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1])
}

如果目标是得分最大，每次合并的两个区间，一定有一个长度为1
通过这个优化，时间复杂度可以变为 O(n^2)

如果目标是得分最小，满足四边形不等式
假设 f[i][j] 在 k=p[i][j] 最优
换句话说 f[i][k]+f[k+1][j] 在 k=p[i][j] 取到最小值

p[i][j-1] <= p[i][j] <= p[i+1][j]

https://www.luogu.com.cn/blog/Hurricane-zjz/solution-p1880

P1063 [NOIP2006 提高组] 能量项链

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

题目描述

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 NN 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 mm，尾标记为 rr，后一颗能量珠的头标记为 rr，尾标记为 nn，则聚合后释放的能量为 m×r×nm \times r \times n（Mars 单位），新产生的珠子的头标记为 mm，尾标记为 nn。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 N=4N=4，44 颗珠子的头标记与尾标记依次为 (2,3)(3,5)(5,10)(10,2)(2,3)(3,5)(5,10)(10,2)。我们用记号 ⊕\oplus 表示两颗珠子的聚合操作，(j⊕k)(j \oplus k) 表示第 j,kj,k 两颗珠子聚合后所释放的能量。则第 44 、 11 两颗珠子聚合后释放的能量为：

(4⊕1)=10×2×3=60(4 \oplus 1)=10 \times 2 \times 3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为：

((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710((4 \oplus 1) \oplus 2) \oplus 3)=10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710。

输入格式

第一行是一个正整数 NN（4≤N≤1004 \le N \le 100），表示项链上珠子的个数。第二行是 NN 个用空格隔开的正整数，所有的数均不超过 10001000。第 ii 个数为第 ii 颗珠子的头标记（1≤i≤N1 \le i \le N），当 i<Ni<N 时，第 ii 颗珠子的尾标记应该等于第 i+1i+1 颗珠子的头标记。第 NN 颗珠子的尾标记应该等于第 11 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式

一个正整数 EE（E≤2.1×109E\le 2.1 \times 10^9），为一个最优聚合顺序所释放的总能量。

样例 #1

样例输入 #1
4
2 3 5 10
样例输出 #1
710

提示

NOIP 2006 提高组 第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[220], ans;
int f[220][220];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i + n] = a[i];
	}
	for (int l = 2; l <= n; l++) {
		for (int i = 0; i + l < 2 * n; i++) {
			int j = i + l;
			for (int k = i + 1; k < j; k++) {
				f[i][j] = max(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j]);
				ans = max(ans, f[i][j]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

题解

这个题和矩阵乘法时间复杂度类似

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

先不考虑环的情况
如果按顺序一次一次做乘法

(2,3)(3,5)(5,10)(10,2)
(2,5)(5,10)(10,2)
(2,10)(10,2)
(2,2)
2*3*5 + 2*5*10 + 2*10*2 = 170

(2,3)(3,5)(5,10)(10,2)
(2,3)(3,5)(5,2)
(2,3)(3,2)
(2,2)
5*10*2 + 3*5*2 + 2*3*2 = 142

结合律 (A * B) * C = A * (B * C)
不是 (A * B) * C = (B * C) * A
这是结合律 交换律 一起使用的到的

f[i][j] 表示把 a[i] a[i+1] .. a[j-1] a[j] 这些数字合并成 a[i] a[j] 两个数字的最小代价
转移方程，一定是先把 a[i] 到 a[k] 的区间合并，把 a[k] 到 a[j] 的区间合并
f[i][j] = max(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j])

处理环形：把数组重复两次

P1220 关路灯

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

题目描述

某一村庄在一条路线上安装了 nn 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。

为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为 1m/s1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：mm）、功率（WW），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

输入格式

第一行是两个数字 nn（表示路灯的总数）和 cc（老张所处位置的路灯号）；

接下来 nn 行，每行两个数据，表示第 11 盏到第 nn 盏路灯的位置和功率。数据保证路灯位置单调递增。

输出格式

一个数据，即最少的功耗（单位：JJ，1J=1W×s1J=1W\times s）。

样例 #1

样例输入 #1
5 3
2 10
3 20
5 20
6 30
8 10
样例输出 #1
270

提示

样例解释

此时关灯顺序为 3 4 2 1 5。

数据范围

1≤n≤501\le n\le50，1≤c≤n1\le c\le n。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, c;
int a[60], s[60];
int f[60][60];
int g[60][60];
int main()
{
	scanf("%d%d", &n, &c);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &a[i], &s[i]);
		s[i] += s[i - 1];
	}
	memset(f, 0x3f, sizeof f);
	memset(g, 0x3f, sizeof g);
	f[c][c] = 0;
	g[c][c] = 0;
	for (int j = 1; j <= n; j++)
	{
		for (int i = j - 1; i > 0; i--)
		{
			int u = s[n] - s[j] + s[i];
			int v = s[n] - s[j-1] + s[i-1];
			f[i][j] = min(f[i+1][j] + (a[i+1]-a[i]) * u, g[i+1][j] + (a[j]-a[i]) * u);
			g[i][j] = min(g[i][j-1] + (a[j]-a[j-1]) * v, f[i][j-1] + (a[j]-a[i]) * v);
		}
	}
	printf("%d\n", min(f[1][n], g[1][n]));
	return 0;
}

题解

5 3
2 10
3 20
5 20
6 30
8 10

5->6   70 * 1
6->3   40 * 3
3->2   20 * 1
2->8   10 * 6
70 * 1 + 40 * 3 + 20 * 1 + 10 * 6 = 270

f[i][j] 表示关掉 第i个 到 第j个 的灯 最小的耗电量
发现还需要记录，最后停在 i 还是停在 j
f[i][j] 表示关掉 第i个 到 第j个 的灯 且最后停在 i 最小的耗电量
g[i][j] 表示关掉 第i个 到 第j个 的灯 且最后停在 j 最小的耗电量

f[i][j] 最后一个关掉的灯，一定是 第i个灯所以可能从 f[i+1][j] 或 g[i+1][j] 转移过来
g[i][j] 最后一个关掉的灯，一定是 第j个灯所以可能从 f[i][j-1] 或 g[i][j-1] 转移过来

如果是从区间 i+1,j 转移到 区间 i,j 期间还开着的灯是
1 ... i    j+1 .. n = s[n] - s[j] + s[i]

如果是从区间 i,j-1 转移到 区间 i,j 期间还开着的灯是
1 ... i-1    j .. n = s[n] - s[j-1] + s[i-1]

如果从第x个灯走到第y个灯，时间是 abs(a[x] - a[y])

P3205 [HNOI2010]合唱队

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

题目描述

为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 nn 个人，第 ii 个人的身高为 hih_i 米（1000≤hi≤20001000 \le h_i \le 2000），并已知任何两个人的身高都不同。假定最终排出的队形是 AA 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：

当 nn 个人全部插入当前队形后便获得最终排出的队形。

例如，有 66 个人站成一个初始队形，身高依次为 1850,1900,1700,1650,1800,17501850, 1900, 1700, 1650, 1800, 1750，
那么小 A 会按以下步骤获得最终排出的队形：

因此，最终排出的队形是 1750,1650,1700,1850,1900,18001750, 1650, 1700, 1850, 1900, 1800。

小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。

请求出答案对 1965082719650827 取模的值。

输入格式

第一行一个整数 nn。
第二行 nn 个整数，表示小 A 心中的理想队形。

输出格式

输出一行一个整数，表示答案  mod 19650827\bmod 19650827 的值。

样例 #1

样例输入 #1
4
1701 1702 1703 1704
样例输出 #1
8

提示

对于 30%30\% 的数据，n≤100n \le 100。
对于 100%100\% 的数据，n≤1000n \le 1000，1000≤hi≤20001000 \le h_i \le 2000。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int p = 19650827;
int n;
int a[1001];
int f[1001][1001];
int g[1001][1001];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		f[i][i] = 1;
	}
	for (int i = n; i >= 1; i--)
	{
		for (int j = i + 1; j <= n; j++)
		{
			f[i][j] = ((a[i] < a[i+1] ? f[i+1][j] : 0) + (a[i] < a[j] ? g[i+1][j] : 0)) % p;
			g[i][j] = ((a[j] > a[j-1] ? g[i][j-1] : 0) + (a[j] > a[i] ? f[i][j-1] : 0)) % p;
		}
	}
	cout << (f[1][n] + g[1][n]) % p << endl;
	return 0;
}

题解

f[i][j] 如果 第i个 人到 第j个人 如果理想队列只有这些人，方案数是多少

P3146 [USACO16OPEN]248 G

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

题目描述

Bessie likes downloading games to play on her cell phone, even though she doesfind the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing.The game starts with a sequence of NN positive integers (2≤N≤2482 \leq N\leq 248), each in the range 1…401 \ldots 40. In one move, Bessie cantake two adjacent numbers with equal values and replace them a singlenumber of value one greater (e.g., she might replace two adjacent 7swith an 8). The goal is to maximize the value of the largest numberpresent in the sequence at the end of the game. Please help Bessiescore as highly as possible!

给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问序列中出现的最大数字的值最大是多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。

输入格式

The first line of input contains NN, and the next NN lines give the sequence

of NN numbers at the start of the game.

输出格式

Please output the largest integer Bessie can generate.

样例 #1

样例输入 #1
4
1
1
1
2
样例输出 #1
3

提示

In this example shown here, Bessie first merges the second and third 1s to

obtain the sequence 1 2 2, and then she merges the 2s into a 3. Note that it is

not optimal to join the first two 1s.

参考代码

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

题解

f[i][j] 表示 i 到 j 合并出的数字最大是什么
可以发现，如果能合并出来，那么合并出来的数字结果是唯一的

P4170 [CQOI2007]涂色

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

题目描述

假设你有一条长度为 55 的木板，初始时没有涂过任何颜色。你希望把它的 55 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 55 的字符串表示这个目标：RGBGR\texttt{RGBGR}。

每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 RRRRR\texttt{RRRRR}，第二次涂成 RGGGR\texttt{RGGGR}，第三次涂成 RGBGR\texttt{RGBGR}，达到目标。

用尽量少的涂色次数达到目标。

输入格式

输入仅一行，包含一个长度为 nn 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

输出格式

仅一行，包含一个数，即最少的涂色次数。

样例 #1

样例输入 #1
AAAAA
样例输出 #1
1

样例 #2

样例输入 #2
RGBGR
样例输出 #2
3

提示

40%40\% 的数据满足 1≤n≤101\le n\le 10。

100%100\% 的数据满足 1≤n≤501\le n\le 50。

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[60];
int f[60][60];
int main()
{
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	for (int i = n; i > 0; i--)
	{
		f[i][i] = 1;
		for (int j = i + 1; j <= n; j++)
		{
			f[i][j] = f[i][j-1] + (s[i] != s[j]);
			for (int k = i; k < j; k++)
			{
				f[i][j] = min(f[i][j], f[i][k] + f[k+1][j]);
			}
		}
	}
	printf("%d\n", f[1][n]);
	return 0;
}

题解

P4170 [CQOI2007]涂色
P7414 [USACO21FEB] Modern Art 3 G
f[i][j] i到j最少染几次
转移，区间可以拼起来
f[i][j] = min(f[i][j], f[i][k]+f[k+1][j])

如果区间的第一个颜色，和最后一个颜色相等，那么涂第一个颜色时，一定可以顺便涂最后一个颜色
if (s[i] == s[j])
{
f[i][j] = f[i][j - 1];
}

P7414 [USACO21FEB] Modern Art 3 G

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

题目描述

厌倦了常规的二维画作（同时也由于作品被他人抄袭而感到失落），伟大的奶牛艺术家牛加索决定转变为更为极简主义的一维风格。她的最新画作可以用一个长为 NN（1≤N≤3001 \leq N \leq 300）的一维数组来描述，其中每种颜色用 1…N1\ldots N 中的一个整数表示。

令牛加索感到沮丧的是，尽管这样，她的竞争对手哞奈似乎已经发现了如何抄袭她的这些一维画作！哞奈会用一种颜色涂在一个区间上，等待颜料干了再涂另一个区间，以此类推。哞奈可以使用 NN 中颜色中的每一种任意多次（也可以不用）。

请计算哞奈抄袭牛加索的最新一维画作所需要的涂色的次数。

输入格式

输入的第一行包含 NN。

下一行包含 NN 个范围在 1…N1 \ldots N 之内的整数，表示牛加索的最新一维画作每个方格上的颜色。

输出格式

输出抄袭这一画作所需要的最小涂色次数。

样例 #1

样例输入 #1
10
1 2 3 4 1 4 3 2 1 6
样例输出 #1
6

提示

样例 1 解释：

在这个样例中，哞奈可以按下列方式进行涂色。我们用 00 表示一个未涂色的方格。

注意在第一次涂色时，哞奈可以同时在前九个方格之外将第十个方格也同时涂上颜色 11，这并不会影响最后的结果。

测试点性质：

供题：Brian Dean，Benjamin Qi

参考代码

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

题解

P4170 [CQOI2007]涂色
P7414 [USACO21FEB] Modern Art 3 G
f[i][j] i到j最少染几次
转移，区间可以拼起来
f[i][j] = min(f[i][j], f[i][k]+f[k+1][j])
if (s[i] == s[j])
{
f[i][j] = f[i][j - 1];
}

P3147 [USACO16OPEN]262144 P

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

题目描述

Bessie likes downloading games to play on her cell phone, even though she doesfind the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing.The game starts with a sequence of NN positive integers (2≤N≤262,1442 \leq N\leq 262,144), each in the range 1…401 \ldots 40. In one move, Bessiecan take two adjacent numbers with equal values and replace them asingle number of value one greater (e.g., she might replace twoadjacent 7s with an 8). The goal is to maximize the value of thelargest number present in the sequence at the end of the game. Pleasehelp Bessie score as highly as possible!

Bessie喜欢在手机上下游戏玩（……），然而她蹄子太大，很难在小小的手机屏幕上面操作。

她被她最近玩的一款游戏迷住了，游戏一开始有n个正整数，(2<=n<=262144)，范围在1-40。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个7合并成一个8)，目标是使得最大的数最大，请帮助Bessie来求最大值。

输入格式

The first line of input contains NN, and the next NN lines give the sequence

of NN numbers at the start of the game.

输出格式

Please output the largest integer Bessie can generate.

样例 #1

样例输入 #1
4
1
1
1
2
样例输出 #1
3

提示

In this example shown here, Bessie first merges the second and third 1s to

obtain the sequence 1 2 2, and then she merges the 2s into a 3. Note that it is

not optimal to join the first two 1s.

参考代码

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

题解

f[i][j]
从左端点是i，合并出数字j，右端点是唯一的，合并不出记 0
如果 a[i] == j
那么不需要合并 f[i][j] = i + 1 // 左闭右开
f[i][j] = f[f[i][j-1]][j-1]

P5851 [USACO19DEC]Greedy Pie Eaters P

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

题目背景

Farmer John has MM cows, conveniently labeled 1…M1 \ldots M, who enjoy the occasional change of pace
from eating grass. As a treat for the cows, Farmer John has baked NN pies (1≤N≤3001 \leq N \leq 300), labeled
1…N1 \ldots N. Cow ii enjoys pies with labels in the range [li,ri][l_i, r_i] (from lil_i to rir_i inclusive),
and no two cows enjoy the exact same range of pies. Cow ii also has a weight, wiw_i, which
is an integer in the range 1…1061 \ldots 10^6.

Farmer John may choose a sequence of cows c1,c2,…,cK,c_1,c_2,\ldots, c_K, after which the
selected cows will take turns eating in that order. Unfortunately, the cows
don't know how to share! When it is cow cic_i's turn to eat, she will consume
all of the pies that she enjoys --- that is, all remaining pies in the interval
[lci,rci][l_{c_i},r_{c_i}]. Farmer John would like to avoid the awkward situation
occurring when it is a cows turn to eat but all of the pies she enjoys have already been
consumed. Therefore, he wants you to compute the largest possible total weight
(wc1+wc2+…+wcKw_{c_1}+w_{c_2}+\ldots+w_{c_K}) of a sequence c1,c2,…,cKc_1,c_2,\ldots, c_K for which each cow in the
sequence eats at least one pie.

题目描述

Farmer John 有 MM 头奶牛，为了方便，编号为 1,…,M1,\dots,M。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 NN 个派请奶牛吃，这 NN 个派编号为 1,…,N1,\dots,N。第 ii 头奶牛喜欢吃编号在 [li,ri]\left[ l_i,r_i \right] 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 ii 头奶牛有一个体重 wiw_i，这是一个在 [1,106]\left[ 1,10^6 \right] 中的正整数。

Farmer John 可以选择一个奶牛序列 c1,c2,…,cKc_1,c_2,\dots,c_K，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 [lci,rci][l_{c_i},r_{c_i}] 中所有剩余的派。Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此，他想让你计算，要使奶牛按 c1,c2,…,cKc_1,c_2,\dots,c_K 的顺序吃派，轮到这头奶牛时她喜欢的派至少剩余一个的情况下，这些奶牛的最大可能体重（wc1+wc2+…+wcKw_{c_1}+w_{c_2}+\ldots+w_{c_K}）是多少。

输入格式

第一行包含两个正整数 N,MN,M；

接下来 MM 行，每行三个正整数 wi,li,riw_i,l_i,r_i。

输出格式

输出对于一个合法的序列，最大可能的体重值。

样例 #1

样例输入 #1
2 2
100 1 2
100 1 1
样例输出 #1
200

提示

样例解释
在这个样例中，如果奶牛 11 先吃，那么奶牛 22 就吃不到派了。然而，先让奶牛 22 吃，然后奶牛 11 只吃编号为 22 的派，仍可以满足条件。

对于全部数据，1≤N≤300,1≤M≤N(N−1)2,1≤li,ri≤N,1≤wi≤1061 \le N \le 300,1 \le M \le \dfrac{N(N-1)}{2},1 \le l_i,r_i \le N,1 \le w_i \le 10^6。
数据范围
对于测试点 2−52-5，满足 N≤50,M≤20N \le 50,M \le 20；

对于测试点 6−96-9，满足 N≤50N \le 50。

USACO 2019 December 铂金组T1

参考代码

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

题解

对于所有没输入的区间，都假设有一个体重为0的牛吃
这样可以要求，最终求出的序列，每个牛只能吃一个Pie，最后一定会选出n个牛

f[i][j] 只考虑第i个Pie到第j个Pie 的最优解 ，这个最优解，不能包含吃[i, j]范围外的牛
那么这个最优解一定恰好包含 j-i+1 个牛
考虑这个区间内，最后一个被吃的是哪个Pie，有 j-i+1 种情况
假设是k

f[i][j] = max(f[i][j], f[i][k-1] + f[k+1][j] + (体重最大 i <= 左端点 <= k <= 右端点 <= j 的牛))

P2924 [USACO08DEC]Largest Fence G

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

题目描述

Farmer John has purchased N (5 <= N <= 250) fence posts in order to build a very nice-looking fence. Everyone knows the best fences are convex polygons where fence posts form vertices of a polygon. The pasture is represented as a rectilinear grid; fencepost i is at integer coordinates (x_i, y_i) (1 <= x_i <= 1,000; 1 <= y_i <= 1000).

Given the locations of N fence posts (which, intriguingly, feature no set of three points which are collinear), what is the largest number of fence posts FJ can use to create a fence that is convex?

For test cases worth 45% of the points for this problem, N <= 65.

Time limit: 1.2 seconds

POINTS: 400

Farmer John的农场里有N（5<=N<=250）个篱笆桩，每个都有独一无二的坐标(xi,yi)（1<=xi,yi<=1000）。他想选择尽量多的篱笆桩来构建他的围栏。这个围栏要美观，所以必须是凸多边形的。那他最多能选多少个呢？

所有的篱笆桩中不存在三点共线。

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 describes fence post i's location with two space-separated integers: x_i and y_i

输出格式

* Line 1: A single integer, the maximum possible number of fence posts that form a convex polygon.

样例 #1

样例输入 #1
6 
5 5 
2 3 
3 2 
1 5 
5 1 
1 1
样例输出 #1
5

提示

A square with two points inside.

The largest convex polygon is the pentagon (2,3), (3,2), (5,1), (5,5), (1,5).

参考代码

题解

P4767 [IOI2000]邮局

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

题目描述

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入格式

第一行包含两个整数：第一个是村庄 VV 的数量，第二个是邮局的数量 PP。

第二行包含 VV 个整数。这些整数是村庄的位置。

输出格式

第一行包含一个整数SS，它是每个村庄与其最近的邮局之间的所有距离的总和。

样例 #1

样例输入 #1
10 5 
1 2 3 6 7 9 11 22 44 50
样例输出 #1
9

提示

对于 40%40\% 的数据，V≤300V \leq 300。

对于 100%100\% 的数据，1≤P≤3001 \leq P \leq 300，P≤V≤3000P \leq V \leq 3000，1≤1 \leq 村庄位置 ≤10000\leq 10000。

参考代码

题解

abc252_g

https://atcoder.jp/contests/abc252/tasks/abc252_g
输入一个排列
问有多少个有根树（1是根）的前序遍历是输入的排列
如果一个点有多个孩子，那么必须从最小的孩子开始DFS

参考代码

题解

CF1114D Flood Fill

https://codeforces.com/problemset/problem/1114/D
https://www.luogu.com.cn/problem/CF1114D

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[5020];
int f[5020][5020];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	n = unique(a + 1, a + 1 + n) - a - 1;
	for (int i = n; i > 0; i--)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if (a[i] == a[j])
			{
				f[i][j] = f[i + 1][j - 1] + 1;
			}
			else
			{
				f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
			}
		}
	}
	cout << f[1][n] << endl;
	return 0;
}

题解

  1. 区间DP
    1. 时间复杂度
      1. O(n2)O(n^2)
      2. O(n3)O(n^3)
    2. 循环顺序
    3. 四边形不等式
    4. 相关题目
      1. P1880 [NOI1995] 石子合并
      2. P1063 [NOIP2006 提高组] 能量项链
      3. P1220 关路灯
      4. P3205 [HNOI2010]合唱队
      5. P3146 [USACO16OPEN]248 G
      6. P4170 [CQOI2007]涂色
      7. P7414 [USACO21FEB] Modern Art 3 G
      8. P3147 [USACO16OPEN]262144 P
      9. P5851 [USACO19DEC]Greedy Pie Eaters P
      10. P2924 [USACO08DEC]Largest Fence G
      11. P4767 [IOI2000]邮局
      12. abc252_g
      13. CF1114D Flood Fill
≡