区间DP：
（1）合并：即将两个或多个部分进行整合，当然也可以反过来。
（2）特征：能将问题分解为能两两合并的形式。
（3）求解：将整个问题舍最优值，枚举合并点，将问题分解为左右两个部分，最后合并的两个部分的最优值得到原问题的最优值。
*例题：
NC13230(合并回文子串)
题目描述：
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可
输入描述:
第一行一个整数T(T ≤ 50)。
接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。
输出描述:
对于每组数据输出一行一个整数表示价值最大的C的价值。
样例：
输入：2aabbaaaaabcaa
输出：45
++++++++++
DP状态分析：
作者：王清楚
链接->>：思路详细分析
具体到Dp[i][j] 有两种情况（单独对于一个串s时）：
s[i] == s[j]：这个时候可以把s[i]和s[j]分别加到原来0的回文子序列的两端，也就是 i+1 到 j-1 这个区间的字符构成的最长回文子序列的两端，此时 dp[i][j]=dp[i+1][j−1]+2;s[i] != s[j]：那么在 {i}i 到 {j}j 这个区间的最长回文子序列中第 {i}i 个字符和第 {j}j 个字符一定不能同时存在，所以是可以扔掉他俩中的某一个的（并不是任意一个），此时
dp[i][j]=max(dp[i+1][j],dp[i][j−1])。
而两个串的合并就是这两种状态转移方程的子状态，具体看代码
++++++++++
AC代码（times = 973ms / 2000ms）：
//区间DP#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>#define LL long long#define mem(x,y) memset(x,y,sizeof(x))const int maxn = 52;const int mod = 1e9 + 7;using namespace std;namespace needs {template<typename T> inline void read(T& ans){T x = 0, f = 1; char c = getchar();while (c < '0' || c>'9') {if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();ans = f * x;}inline void read(string& st1){char ch = getchar(); st1 = "";while (!((ch >= 'a') && (ch <= 'z'))) ch = getchar();while ((ch >= 'a') && (ch <= 'z')) st1 += ch, ch = getchar();}}using namespace needs;int dp[maxn][maxn][maxn][maxn];//i,j,k,l;前一个串（a串）的第 i 个字符到第 j 个字符后一个串（b串）的第 k 个字符到第 l 个字符能否组成一个回文串int main(){int t;read(t);while (t--){mem(dp, 0);string a, b; read(a), read(b);int alen = a.size() , blen = b.size() , ans = 0;a = ' ' + a; b = ' ' + b;//字符串后移，防止下标-1的出现for (int lena = 0; lena <= alen; ++lena)//枚举a串的长度for (int lenb = 0; lenb <= blen; ++lenb)//枚举b串的长度for (int i = 1; i <= alen - lena + 1; ++i)//枚举a串区间的起始点for (int k = 1; k <= blen - lenb + 1; ++k)//枚举b串区间的起始点{int j = i + lena - 1, l = k + lenb - 1;//根据各串的起始点和长度求出区间的结束点if (lena + lenb <= 1) dp[i][j][k][l] = 1;//长度为一，本身一定是本身的回文串else{//四种情况if (a[i] == a[j]) dp[i][j][k][l] |= dp[i + 1][j - 1][k][l];//往 a[i+1] 到 a[j−1] 和 b[k] 到 b[l] 构成的串的两端加上 a[i] 和 a[j] 两个字符if (a[i] == b[l]) dp[i][j][k][l] |= dp[i + 1][j][k][l - 1];//往 a[i+1] 到 a[j] 和 b[k] 到 b[l−1] 构成的串的两端加上 a[i] 和 b[l] 两个字符if (a[j] == b[k]) dp[i][j][k][l] |= dp[i][j - 1][k + 1][l];//往 a[i] 到 a[j−1] 和 b[k+1] 到 b[l] 构成的串的两端加上 b[k] 和 a[j] 两个字符if (b[k] == b[l]) dp[i][j][k][l] |= dp[i][j][k + 1][l - 1];//往 a[i] 到 a[j] 和 b[k+1] 到 b[l−1] 构成的串的两端加上 b[k] 和 b[l] 两个字符}if(dp[i][j][k][l]) ans = max(ans, lena + lenb);//更新答案}printf("%d\n", ans);//圆满结束}return 0;}
NC16129(小小粉刷匠)
题目描述 ：
“lalala,我是一个快乐的粉刷匠”,小名一边快活地唱着歌,一边开心地刷着墙",兴致突然被打断,“小名,你今天如果刷不完这一栋楼的墙，那么你就等着被炒鱿鱼吧”,老板声嘶力竭的吼着。苦恼的小名因为不想被炒鱿鱼,所以希望尽量快地刷完墙,由于他本人的数学基础很差,他现在请你来帮助他计算最少完成每一堵墙需要刷多少次。每一面墙有n个段,对于每个段指定一个目标颜色ci。刚开始的时候所有的墙壁为白色,我们现在有一个刷子,刷子长度为k,刷子每次可以选择一种颜色,然后选择段数为(1～k)连续的墙段刷成选择的一种颜色。我们现在想要知道，为了把墙变成目标颜色，最少刷多少次(保证指定的目标颜色一定不为白色)。
*TIPS: 看懂的可以尝试同题型题目巩固一下 ，不懂的可以先做 简单版NC19909，同类型，相比这题简单。
输入描述:
对于每一个案例,我们第一行包括两个整数n,k(1<=n<=100,1<=k<=50,k<n),表示墙的长度为n,刷子的长度为k。第二行输入n个整数(c1c2…cn),(1<=ci<=256),表示对于墙的每一段指定的颜色。``
输出描述:
输出一个数,表示小名最少刷多少次。
样例：
输入一：3 31 2 1
输出一：2
++++++++++
输入二：5 45 4 3 3 4
输出二：3
++++++++++
DP状态分析：
作者： 回归的梦想
链接： 思路来源
dp[i][j]表示第i个位置到第j个位置所需要最小步数
(n为刷子的长度，k为枚举的区间断点)
第一种情况：
当 n>=len时,（len为我们当前枚举的长度），我们可以直接画完，我们在枚举断点k时，先判断a[i]==a[k]，如果相等有dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j])，最少操作次数就是讲第i个与第k个一起涂，所以区间[i,j]中做端点i就不用考虑了
第二种情况：
当 n<len时，我们的刷子长度不够，所以直接将区间拆分即可 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
具体分析见代码
++++++++++
AC代码（times = 4ms / 1000ms）：
//区间DP#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>#define LL long long#define mem(x,y) memset(x,y,sizeof(x))const int maxn = 1e2 + 7;const int mod = 1e9 + 7;using namespace std;namespace needs {template<typename T> inline void read(T& ans){T x = 0, f = 1; char c = getchar();while (c < '0' || c>'9') {if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();ans = f * x;}inline void read(string& st1){char ch = getchar(); st1 = "";while (!((ch >= 'a') && (ch <= 'z'))) ch = getchar();while ((ch >= 'a') && (ch <= 'z')) st1 += ch, ch = getchar();}}using namespace needs;int date[maxn],dp[maxn][maxn];//i,j;表示以i为起始点到j位置所需要的最少步数int main(){int n, k; read(n), read(k);mem(dp, 0);for (int i = 1; i <= n; ++i)read(date[i]), dp[i][i] = 1;//初始化for (int len = 2; len <= n; ++len)//枚举区间的长度for (int i = 1; i <= n - len + 1; ++i)//枚举区间的起始点{int j = i + len - 1;//根据长度和起始点计算结束点dp[i][j] = dp[i + 1][j] + 1;//假设date[i]!=date[j],所以扩张一个长度，需要dp[i+1][j]+1，//答案会在断点枚举的时候验证，更新if (k >= len) //刷子长度小于区间的长度for (int k = i + 1; k <= j; ++k)//枚举断点{if (date[i] == date[k]) dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);}//更新答案// 如若date[i] == date[k]，且刷子长度够长，//则粉刷date[i+1][k]的时候等同于粉刷date[i][k],//但此时date[i][k]无意义，所以答案要从datep[i+1][k]中更新，//最后在加上断点后区间所需的步数进行更新即可else//区间太长，分割区间，枚举断点，更新答案for (int k = i + 1; k <= j; ++k)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);}printf("%d\n", dp[1][n]);//圆满落幕return 0;}
NC19973([HAOI]玩具取名)
题目描述:
某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。
输入描述:
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字。
输出描述:
一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）
如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”
样例：
输入：1 1 1 1IIWWWWIGIIII
输出：IN
++++++++++
DP状态分析：
作者： 回归的梦想
链接： 思路来源
dp[i][j][k]表示区间[i , j]是否是由k转化而来的 ，is[i][j][k]表示i是否可以用 j , k 两个字母代替
区间 [l , r], 中间点为k ，z，z1，z2 为 1~4，表示为WING(关于z, z1 , z2 可以根据代码更好理解)
如果左区间[l,k+1]可以由z1转化（即代码dp[l][k][z1]），右区间[k+1,r]可以由z2转化 (代码dp[k+1][r][z2]) , z可以用z1和z2来代替（代码（原作者错误，已更改）is[z][z1][z2]），那是不是就说明区间[l,r]是由z转化的 -》》(相当于z1，z2是一个中转站，用来将区间[l,r]与z联系在一起)
tips:结合代码理解
具体内容见代码
++++++++++
AC代码 （times = 74ms/1000ms）
//区间DP#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>#define LL long long#define mem(x,y) memset(x,y,sizeof(x))const int maxn = 2e2 + 7;const int mod = 1e9 + 7;using namespace std;namespace needs {template<typename T> inline void read(T& ans){T x = 0, f = 1; char c = getchar();while (c < '0' || c>'9') {if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();ans = f * x;}inline void read(string& st1){char ch = getchar(); st1 = "";while (!((ch >= 'a') && (ch <= 'z')) && !((ch >= 'A') && (ch <= 'Z'))) ch = getchar();while (((ch >= 'a') && (ch <= 'z')) || ((ch >= 'A') && (ch <= 'Z'))) st1 += ch, ch = getchar();}}using namespace needs;bool dp[maxn][maxn][5], is[5][5][5];//dp[i][j][k]表示区间[i , j]是否是由k转化而来的 ，is[i][j][k]表示i是否可以用 j , k 两个字母代替int n[5];int getnum(char date)//求字母对应的数字{if (date == 'W') return 1;if (date == 'I') return 2;if (date == 'N') return 3;if (date == 'G') return 4;}int main(){mem(dp, false), mem(is, false);//初始化for (int i = 1; i <= 4; ++i) read(n[i]);//读入种类for (int i = 1; i <= 4; ++i)for (int j = 1; j <= n[i]; ++j){char x, y;x = getchar(), y = getchar(), getchar();is[i][getnum(x)][getnum(y)] = true;// 根据题意，读入数据，数字i对应的字母可以由x,y转换而来，标记为true}string date; read(date);//读入名字int length = (int)date.size();date = ' ' + date;//防止下标-1的出现，后移for (int i = 1; i <= length; ++i) dp[i][i][getnum(date[i])] = true;//每个字母都可以转成自己，例如：W->Wfor (int len = 2; len <= length; ++len)//枚举区间长度for (int i = 1; i <= length - len + 1; ++i)//枚举区间起始点for (int k = i, j = i + len - 1; k < j; ++k)//计算区间结束点j，枚举区间断点for (int z = 1; z <= 4; ++z)//枚举转化字母for (int z1 = 1; z1 <= 4; ++z1)//枚举被转化字母for (int z2 = 1; z2 <= 4; ++z2)//枚举被转化字母if (is[z][z1][z2] && dp[i][k][z1] && dp[k + 1][j][z2])//字母z可以由z1和z2转化而来，同时可以找到断点左区间可以由z1转化，//右区间可以由z2转化，等效替代，得出总区间可以由z转化而来dp[i][j][z] = true;bool tag = false;if (dp[1][length][1]) printf("W"), tag = true;if (dp[1][length][2]) printf("I"), tag = true;if (dp[1][length][3]) printf("N"), tag = true;if (dp[1][length][4]) printf("G"), tag = true;if (!tag) printf("The name is wrong!");//输出结束return 0;}
NC8([SCOI]字符串折叠)
题目描述：
折叠的定义如下：
一个字符串可以看成它自身的折叠。记作S = S
X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB
给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。
输入描述:
仅一行，即字符串S，长度保证不超过100。
输出描述:
仅一行，即最短的折叠长度。
样例：
输入：NEERCYESYESYESNEERCYESYESYES
输出：14
++++++++++
DP状态分析：
dp[l][r]表示l~r的最短折叠长度
dp[l][r]=min(r-l+1,dp[l][k]+dp[k+1][r]) (l<=k<r)
当区间[k+1,r]可以由区间[l,k]重复时，dp[l][r]=min(dp[l][r],dp[l][k]+2+getnum((r-l+1)/(k-l+1)) —》》》2是指括号占的位数， getnum是指系数所占位数
具体分析见代码
++++++++++
AC代码（times = 3ms / 1000ms）
#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>#define LL long long#define mem(x,y) memset(x,y,sizeof(x))const int maxn = 1e2 + 7;const int mod = 1e9 + 7;using namespace std;namespace needs {template<typename T> inline void read(T& ans){T x = 0, f = 1; char c = getchar();while (c < '0' || c>'9') {if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();ans = f * x;}inline void read(string& st1){char ch = getchar(); st1 = "";while (!((ch >= 'a') && (ch <= 'z')) && !((ch >= 'A') && (ch <= 'Z'))) ch = getchar();while (((ch >= 'a') && (ch <= 'z')) || ((ch >= 'A') && (ch <= 'Z'))) st1 += ch, ch = getchar();}}using namespace needs;int dp[maxn][maxn];string date;inline bool check(int l, int k, int r)//判断是否满足折叠条件// 要想满足，只要断点左边和断点右边的字符串成周期相等即可{if ((r - l + 1) % (k - l + 1)) return false;for (int i = k + 1; i <= r; ++i,++l)if (date[l] != date[i]) return false;return true;}inline int getnum(int x)//返回系数占据长度{if (x < 10) return 1;if (x < 100) return 2;return 3;}int main(){mem(dp, 0x6f);//初始化，字符串最长为100read(date);int len = (int)date.size();date = ' ' + date;//防止下标-1，字符串后移for (int i = 1; i <= len; ++i) dp[i][i] = 1;//自己可以变自己for (int length = 2; length <= len; ++length)//枚举区间长度for (int i = 1; i <= len - length + 1; ++i)//枚举区间起始点{int j = i + length - 1;//根据长度，起始点计算区间结束点for (int k = i; k < j; ++k)//枚举区间断点{dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);//无折叠状态合并(如若dp未初始化，min会导致结果出错)if (check(i, k, j)) dp[i][j] = min(dp[i][j], dp[i][k] + 2 + getnum(length / ((k - i) + 1)));//满足折叠条件，折叠内容长度+括号长度+系数所占长度}}printf("%d\n", dp[1][len]);//圆满return 0;}
补充一题（CF983B）
这里就不解释了，你们可以先去看题，不懂再回来，这里直接上AC代码：
#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>const int maxn = (int)5e3 + 7;const int mod = (int)1e9 + 3;using namespace std;namespace tools {#define ll long long#define mem(x,y) memset(x,y,sizeof(x))#define pii pair<int, int>#define pai 3.141592653589793#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)const ll INF = 0x3f3f3f3f3f3f3f3f;const int inf = 0x3f3f3f3f;using namespace std;template<typename T> inline T tmax(T x, T y, T z) {return max(x, max(y, z)); }template<typename T> inline T tmin(T x, T y, T z) {return min(x, min(y, z)); }template<typename T> inline void debug(T x, T y) {cout << x << " " << y << endl; }template<typename T> inline void debug(T x) {cout << x << endl; }template<typename T> inline void write(T x) {if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10); putchar(x % 10 + '0');}template<typename T> inline void print(T x) {write(x); putchar('\n'); }template<typename T> inline void read(T& ans) {T x = 0, f = 1; char c = getchar();while (c < '0' || c>'9') {if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar(); ans = f * x;}inline ll read() {ll s = 0, bj = 0; char ch = getchar();while (ch < '0' || ch>'9')bj |= (ch == '-'), ch = getchar();while (ch >= '0' && ch <= '9')s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return bj ? -s : s;}}using namespace tools;int dp[maxn][maxn], date[maxn], ans[maxn][maxn], n, t;int main(){read(n);for (int i = 1; i <= n; ++i)read(date[i]), dp[i][i] = ans[i][i] = date[i];for (int i = 2; i <= n; ++i)for (int l = 1, r; r = l + i - 1, l <= n - i + 1; ++l)ans[l][r] = ans[l + 1][r] xor ans[l][r - 1], dp[l][r] = tmax(ans[l][r], dp[l + 1][r] , dp[l][r - 1]);read(t);while (t--)print(dp[read()][read()]);return 0;}
