区间dp
\(Part\) \(1\):区间dp？
利用一个常见的区间dp问题来寻找其与其他dp的区别。
石子合并 :
先不考虑环上，就只看一条链的情况，要求将 \(1\) ~ \(n\) 的石子合并成一颗，每次合并代价是当前两颗石子重量之和，问最大和最小代价。
假设我们现在还不会区间dp，我们考虑用其他dp来解决这个问题：
\(0\).首先考虑贪心的正确性……
\(1\).线性dp，状态 \(dp_i\) 表示合并了前 \(i\) 颗石子的最大 \(/\) 最小代价，\(dp_i\) 可以从 \(j<i\) 的 \(dp_j\) 转移过来，那合并 \(j+1\) ~ \(i\) 的最大 \(/\) 最小代价 \(……\)
发现合并 \(j+1\) ~ \(i\) 的最优代价还是个dp，而一般的线性dp这部分代价都是可以直接计算的，感觉不太可以直接线性dp 。
\(2\).状压dp，\(dp_{sta}\) 表示合并状态为 \(sta\) 的最小代价？\(……\) （这都什么东西）
\(3\).背包？数位dp？\(tree\)-\(dp\) ？插头dp？统统白瞎！
这么看来，还是继续考虑贪心的正确性吧 \(……\)
此时我们急需一个足够优秀的全新的dp类型来解决这类问题，想想这类问题有什么特点，在尝试线性dp的过程中，当我们需要从 \(dp_l\) 转移到 \(dp_r\) 时，不仅要知道 \(dp_l\) 的值，还需要知道一个 \(dp_{l+1,r}\) 的值表示合并了区间 \(l+1\) ~ \(r\) 的最优代价，进而我们想到，如果我们知道了 \(dp_{l,r}\) 表示合并了区间 \(l\) ~ \(r\) 的最优代价该如何转移，那么 \(dp_{1,n}\) 即为所求的答案 。
考虑我们是合并两个石子，所以当 \(l=r\) 时的dp值显然是 \(v_l\) ，而对于长度大于等于 \(2\) 的区间来说，决策过程无非就是先和并左边一段和右边一段，再将左右两边合并，代价为 \(\sum_{i=l}^{r}{v_i}\) ，于是我们枚举断点 \(l\le k\lt r\) ，则 \(dp_{l,r}=min(dp_{l,k}+dp_{k+1,r})+\sum_{i=l}^{r}{v_i}\) ，理解成线性dp就是对于 \(l\le k\lt r\) ，可以从 \(dp_{l,k}\) 转移到 \(dp_{l,r}\) ，代价是 \(dp_{k+1,r}\) 。
对于线性dp \(dp_i\) 来说转移方向是线性的，例如从小向大转移，对于 \(tree\)-\(dp\) 来说转移方向是从儿子转移到父亲，而对于区间dp来说，是从长度小的区间转移到长度大的区间。
回过头来考虑如何实现本题，首先环上问题的经典做法：拆环为链，比如对于 \(n=5\) ，我们可以将环变成长度为 \(10\) 的链 \(1,2,3,4,5,1,2,3,4,5\) ，这样再做区间dp，答案就是区间 \(dp_{1,5}\) ，\(dp_{2,6}\) ，\(dp_{3,7}\) ，\(dp_{4,8}\) ，\(dp_{5,9}\) 的最大值。
然后是如何实现区间dp ，一般有 \(2\) 种实现方法： \(for\) 循环和记忆化搜索，代码如下：
//记忆化搜索:
int DP1(int l,int r){
if(dp[l][r]!=INF)return dp[l][r];
if(l==r)return dp[l][r]=0;
for(int k=l;k<r;++k)dp[l][r]=min(dp[l][r],DP1(l,k)+DP1(k+1,r));
dp[l][r]+=sum[r]-sum[l-1];
return dp[l][r];
}
//for循环
for(int len=2;len<=n;++len)//从小到大枚举区间长度
for(int l=1,r=len;r<=n<<1;++l,++r)//枚举长度为len的区间
for(int k=l;k<r;++k)//枚举断点
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
\(for\) 循环还有一种更简单的写法，发现转移到 \(dp_{l,r}\) 所依赖的状态 \(dp_{l,k}\) 和 \(dp_{k+1,r}\) 都是左端点大于等于 \(l\) 且右端点小于等于 \(r\) ，所以我们可以从后往前枚举 \(l\) ，再从前往后枚举 \(r\) ：
for(int l=n;l;--l)for(int r=l;r<=n;++r)
//Updates
这就是最基础的区间dp模板了，时间复杂度是 \(O(n^3)\) 的，在转移时只涉及到了区间的合并与分裂，而在别的题目中，还有更多的区间dp的性质与套路。
\(Part\) \(2\) ：区间dp常见套路
\(Part\) \(2.1\) ：区间合并
区间合并是区间dp最为基础的模型，其特征是对于 \(dp_{l,r}\) ，转移是枚举一个断点 \(k\) 将区间 \(l\) ~ \(k\) 与区间 \(k+1\) ~ \(r\) 的答案合并起来贡献到区间 \(l\) ~ \(r\) 。
此类问题比较简单，大多数题目都与石子合并没有什么差异。
\(Part\) \(2.1.1\) ：248 G
直接 \(dp_{l,r}\) 表示合并了区间 \(l\) ~ \(r\) 的数位多少，如果无法合并就为 \(0\) ，然后直接枚举断点。
\(Part\) \(2.1.2\) ：凸多边形的划分
仔细思考一下我们划分三角形的过程：由于每条边都在一个三角形里，我们钦定第一个三角形有一条边是 \(1\) - \(n\) ，那么第一个三角形的选取就相当于是在 \(2\) ~ \(n-1\) 中选一个点 \(k\) 当作一个权值为 \(a_1\times a_k\times a_n\) 的三角形，然后由于不能重叠，所以这个三角形将原多边形划分成两个新的多边形，第一个多边形的点集是是区间 \(1\) ~ \(k\) ，第二个多边形的点集是区间 \(k\) ~ \(n\) ，额，这不就是区间dp吗？定义dp状态 \(dp_{l,r}\) 表示将点集 \(l\) ~ \(r\) 构成的多边形划分成 \(r-l+1-2\) 个三角形的最小代价，每次钦定一个区间进行划分的第一个三角形包含边 \(l\) - \(r\) ，然后枚举三角形的另外一个顶点 \(k\) ，转移方程如下：
\(dp_{l,r}=min_{k=l+1}^{r-1}(dp_{l,k}+dp_{k,r}+a_l\times a_k\times a_r)\) 。
这道题主要难在不太容易想到钦定最开始选的三角形中的一条边使得分裂出来的多边形的点集是一段连续的区间，然后进行区间dp。
\(Part\) \(2.2\) ：取其中一个端点或者取两端
此类问题的描述通常是每次可以在左右端点取走 \(/\) 插入一个点，于是我们会考虑 \(dp_{l,r}\) 要么是 \(dp_{l,r-1}\) 在右端点插入，要么是 \(dp_{l+1,r}\) 在左端点插入，要么是 \(dp_{l+1,r-1}\) 在两边都插入。
\(Part\) \(2.2.1\) ：矩阵取数游戏
显然每一行之间是独立的，每次从行首或行尾取让我们想到此类区间dp套路，转移就很简单了。
\(Part\) \(2.2.2\) ：合唱队
每次插到左端或右端！思路还是很明显，\(dp_{l,r,0/1}\) 表示现在队伍为理想队形中的 \(l\) ~ \(r\) 段，最后一个插入的在 \(l\) \(/\) \(r\) 的合法方案数，转移时讨论一下 \(h_l\) ，\(h_{l+1}\) ，\(h_{r-1}\) ，\(h_r\) 之间的大小关系即可：
if(h[l+1]>h[l])Update(dp[l][r][0],dp[l+1][r][0]);
if(h[r]>h[l])Update(dp[l][r][0],dp[l+1][r][1]);
if(h[l]<h[r])Update(dp[l][r][1],dp[l][r-1][0]);
if(h[r-1]<h[r])Update(dp[l][r][1],dp[l][r-1][1]);
\(Part\) \(2.2.3\) ：Coloring Brackets
此题其实同时涉及了区间合并与取左右端点，如果区间 \(l\) ~ \(r\) 为合法括号序列，则存在两种情况：
\(1\). \(s_l='('\) ，\(s_r=')'\) ，即区间 \(l+1\) ~ \(r-1\) 也是一段合法的括号序列，此时应去掉左右端点，由 \(dp_{l+1,r-1}\) 转移而来。
\(2\). 区间 \(l\) ~ \(r\) 是由两个合法的括号序列合并而来，此时我们应该找到一个断点 \(k\) ，由区间 \(l\) ~ \(k\) 和区间 \(k+1\) ~ \(r\) 的合法方案合并而来。
直接定义状态 \(dp_{l,r,0/1/2,0/1/2}\) 表示考虑了区间 \(l\) ~ \(r\) ，左右端点染色情况分别为 \(0/1/2\) 的方案数，其中区间 \(l\) ~ \(r\) 是一个合法的括号序列。
\(Part\) \(2.3\) ：完全计算每一次决策对全局代价产生的影响
实在不知道起什么标题了。
在我们做一些动态规划问题时，经常会发现我们当前决策的代价通过我们目前的状态无法计算出来，以一道题为例：
首先发现已经关掉的路灯显然是连续的一段，那么我们考虑区间dp，dp状态为 \(dp_{l,r,0/1}\) ：关掉了路灯 \(l\) ~ \(r\) 当前站在 \(l/r\) 的最小损失，那么就是从 \(l+1\) ~ \(r\) 或者 \(l\) ~ \(r-1\) 转移过来，那么转移的代价呢？是当前时间 \(t\) 乘以功率 \(v_i\) ，欸，不对劲啊，我们的状态里似乎没有 \(t\) 啊，加上 \(t\) 这一维会使复杂度变得无法接受。
那我们就再定义一个 \(tp_{l,r,0/1}\) 表示达到状态 \(dp_{l,r,0/1}\) 的最小时间，这样不就知道 \(t\) 了吗？要相信假做法也能拿高分。（实测在甲虫这道题中可以拿到 \(80\) 的好成绩）
来思考一下为什么我们会遇到这样的问题，在每次决策的过程中，所有还未关掉的灯都会耗时，所以每次决策的代价并不是关掉的灯的总功耗，而是所有没有关掉的灯的总功率 \(\times\) 这次决策的耗时，那么转移方程就很简单了：
\(dp_{l,r,0}=min(dp_{l+1,r,0}+(pos_{l+1}-pos_i)\times(sum-\sum_{i=l+1}^{r}v_i),dp_{l+1,r,1}+(pos_r-pos_l)\times(sum-\sum_{i=l+1}^{r}{v_i}))\) ，
\(dp_{l,r,1}=min(dp_{l,r-1,0}+(pos_r-pos_l)\times(sum-\sum_{i=l}^{r-1}{v_i}),dp_{l,r-1,1}+(pos_r-pos_{r-1})\times(sum-\sum_{i=l}^{r-1}{v_i}))\) 。
\(Part\) \(2.3.1\) ：Sue 的小球
和上题基本同理，就是写起来复杂一点。
\(Part\) \(2.3.2\) ：甲虫
此题相比前几题多出了一个问题：我们可以不喝完所有的水滴，那么当我们 "预期" 喝的水滴的数量改变时，每次决策造成的水滴蒸发量也会有所区别，那该怎么办呢？发现题目中的 \(0\le n\le 300\) ，目前我们区间dp的复杂度只有 \(O(n^2)\) ，那我们直接暴力枚举预期喝到了多少滴水，每次区间dp，答案取个 \(max\) ，时间复杂度 \(O(n^3)\) 。
\(Part\) \(2.4\) ：涂色问题
\(problem\)：涂色
首先可以发现答案上界为 \(n\) ，那么来考虑在最优解中每次的涂色区间 \(l\) ~ \(r\) 有什么性质，首先这次涂色的颜色一定就是 \(s_l\) （\(s_r\)），其次不同的两个区间的关系只能是包含或者毫不相关，不存在两个仅仅是相交的区间，所以如果区间 \(l\) ~ \(r\) 满足 \(s_l=s_r\) ，那么就可以在涂 \(l\) 或者涂 \(r\) 的时候顺便涂一下另一个变成涂 \(l\) ~ \(r\) ，也就是说此时 \(dp_{l,r}\) 可以由 \(dp_{l+1,r}\) 或者 \(dp_l,r-1\) 转移过来。
而对于所有区间，都可以枚举断点 \(k\) ，转移为 \(dp_{l,r}=min_{k=l}^{r-1}(dp_{l,k}+dp_{k+1,r})\) 。
\(Part\) \(2.4.1\) ：\(problem\) : 给你一个栈，要查询 \(n\) 次栈顶，每次查询之前你可以进行若干次操作：向栈里插入随便一个数或者弹出栈顶（如果存在），要求第 \(i\) 次查询的栈顶为 \(a_i\) ，求至少插入多少次使满足条件？（ \(n\le 100\) ，\(a_i\le 100\) ，多组数据满足 \(t\le 200\) ）
和涂色一模一样，不会换个外皮就不会了吧？
贴个代码：
//...
int T,n,a[N],dp[N][N];
int DP(int l,int r){
if(dp[l][r]!=-1)return dp[l][r];
if(l==r)return dp[l][r]=1;
dp[l][r]=r-l+1;
if(a[l]==a[r])dp[l][r]=min(DP(l+1,r),DP(l,r-1));
for(int k=l;k<r;++k)dp[l][r]=min(dp[l][r],DP(l,k)+DP(k+1,r));
return dp[l][r];
}
//...
signed main(){
read(T);
for(int i=1;i<=T;++i){
read(n);
for(int i=1;i<=n;++i)read(a[i]);
memset(dp,-1,sizeof(dp));
printf("Case %d: %d\n",i,DP(1,n));
}return 0;
}
\(Part\) \(2.5\) ：区间限制
此类问题通常是如果区间一些区间满足了某些限制，那么就可以获得一定的价值，求最大能获得的价值。
考虑此类区间dp如何设计状态及转移，对于限制来说，最简单的方法就是将限制写进dp状态里，然后我们去枚举区间内的点 \(k\) ，钦定点 \(k\) 使得这个区间满足了某些限制条件，称为 "满足点" ，那么这个满足点 \(k\) 能得到的新的贡献就是对于一组限制 ( \(l\) , \(r\) , \(lim\) , \(val\) ) ，其中 \(l\le k \le r\) ，\(lim_k\supseteq lim\) ，就可以得到这个 \(val\)，用人话说，就是我们将我们能得到的价值在这个枚举的满足点 \(k\) 处得到。这时候就有一个疑问了：那一组限制的价值不会重复得到吗？答案是不会，仔细观察一下我们的转移方程：
\(dp_{l,r}=\min_{k=l+1}^{r-1}(dp_{l,k-1}+dp_{k+1,r}+val_{l,r,k})\) ，我们保证了我们在 \(k\) 点得到的价值的区间都包含了 \(k\) 点，所以必定不会被在 \(dp_{l,k-1}\) 和 \(dp_{k+1,r}\) 中得到。
感觉十分抽象，所以我们在具体题目中继续进行解释。
\(Part\) \(2.5.1\) ：Greedy Pie Eaters P
这道题中对区间的限制是若想得到第 \(i\) 头奶牛的价值 \(w_i\) ，必须保证在它开始吃时区间 \(l_i\) ~ \(r_i\) 至少还有一个派，等等，至少还有一个派？那我们的满足点在此题中不就是这个点没有被吃掉，使得区间 \(l\) ~ \(r\) 满足了区间内至少还有一个点，所以dp方程就很简单了：\(dp_{l,r}\) 表示在区间 \(l\) ~ \(r\) 内吃派能得到的最大价值，转移如下：
\(dp_{l,r}=\min_{k=l+1}^{r-1}(dp_{l,k-1}+dp_{k+1,r}+maxval_{l,r,k})\)
其中 \(maxval_{l,r,k}\) 表示对于所有 \(1\le i \le m\) ，满足 \(l\le l_i\le k\le r_i\le r\) 的最大的 \(w_i\) 。现在的问题就是如何处理出来 \(maxval_{l,r,k}\) ，其实也很简单，考虑对于每一个 \(1\le i \le m\) ，所有能得到这个贡献的三元组 \((l,r,k)\) 都满足了 \(l\le l_i\le r_i\le r\) ，\(l_i\le k\le r_i\) ，所以直接按区间长度从小到大更新一下就好了（也可以理解为一个简单的区间dp），代码如下：
for(int i=1;i<=m;++i){
read(w);read(l);read(r);
for(int k=l;k<=r;++k)f[l][r][k]=w;
}
for(int len=2;len<=n;++len)//区间长度从小到大
for(int l=1,r=len;r<=n;++l,++r)for(int k=l;k<=r;++k)
f[l][r][k]=max(f[l][r][k],max(f[l+1][r][k],f[l][r-1][k]));
dp部分也是很容易实现的：
int DP(int l,int r){
if(l>r)return 0;
if(dp[l][r]!=-1)return dp[l][r];
if(l==r)return dp[l][r]=f[l][r][r];
dp[l][r]=0;
for(int k=l;k<=r;++k)dp[l][r]=max(dp[l][r],DP(l,k-1)+DP(k+1,r)+f[l][r][k]);
return dp[l][r];
}
总时间复杂度 \(O(nm+n^3)\) 。
\(Part\) \(2.5.2\) ：MYJ
先看此题的限制：对于所有 \(1\le i\le m\) 来说，若想让这个人来洗车，那么必须满足区间 \(a_i\) ~ \(b_i\) 之间至少有一个数小于等于 \(c_i\) ，跟上一道题基本系出同门，不过一个人洗车的价值并不是固定的，那我们枚举满足点 \(k\) 的时候怎么确定 \(k\) 的数值呢？对于 \(dp_{l,r}\) 这个状态很难处理这个问题，所以我们直接将满足点的数值离散化之后写进dp状态！\(dp_{l,r,w}\) 表示确定了区间 \(l\) ~ \(r\) 的数值，最小值是 \(w\) 的最大代价，写出转移方程如下：
\(dp_{l,r,w}=\max_{k=l+1}^{r-1}(dp_{l,k-1,x}+dp_{k+1,r,y}+w\times num_{l,r,k,w})\) ，其中满足 \(x\ge w\land y\ge w\) ， \(num_{l,r,k,w}\) 是指对于所有 \(1\le i\le m\) ，满足 \(l\le a_i\le k\le b_i\le r \land c_i\ge w\) 的 \(i\) 的个数。
思考如何处理出 \(num_{l,r,w,k}\) ，首先如果直接处理的话时间复杂度和空间复杂度都是 \(50^3\times 4000=5\times 10^7\) 的，其实还有一种更简单的方法，我们可以先处理出 \(cnt_{l,r,w}\) 表示所有 \(1\le i\le m\) 中满足 \(l\le a_i\le b_i\le r\land c_i\ge w\) 的 \(i\) 的个数，简单容斥一下就是 \(num_{l,r,k,w}=cnt_{l,r,w}-cnt_{l,k-1,w}-cnt_{k+1,r,w}\) 。
目前我们这个dp需要枚举每个区间，枚举 \(x\) 和 \(y\) ，枚举断点 \(k\) ，时间复杂度不能接受，但是很显然 \(dp_{l,k-1,x}\) 和 \(dp_{k+1,r,y}\) 这两个东西是可以前缀和优化的，记 \(ma_{l,r,w}=\max_{x\ge w}(dp_{l,r,w})\) ，时间复杂度就变成了 \(O(n^3m)\) 的。
然后这道题真正恶心的地方就是要输出方案，所以我们需要记录 \(dp_{l,r,w}\) 得到最大值的满足点 \(pos_{l,r,w}\) 和前缀最大 \(ma_{l,r,w}\) 在哪里取到，记为 \(pre_{l,r,w}\) ，实现起来细节比一般区间dp题多一些：
//Up表示离散化之后c[i]的最大值
for(int i=Up;i;--i)for(int l=1;l<=n;++l)//计算cnt数组
for(int r=l;r<=n;++r)cnt[l][r][i]+=cnt[l][r][i+1];
for(int l=1;l<=n;++l)for(int r=l;r<=n;++r)pre[l][r][Up+1]=Up;
for(int i=Up;i;--i){
for(int l=1;l<=n;++l){
dp[l][l][i]=vec[i-1]*cnt[l][l][i];
if(dp[l][l][i]>Max[l][l][i+1]){
Max[l][l][i]=dp[l][l][i];
pre[l][l][i]=i;
}else{Max[l][l][i]=Max[l][l][i+1];pre[l][l][i]=pre[l][l][i+1];}
}
for(int l=n;l;--l)for(int r=l+1;r<=n;++r){
for(int k=l;k<=r;++k)
if(Max[l][k-1][i]+Max[k+1][r][i]+vec[i-1]*(cnt[l][r][i]-cnt[l][k-1][i]-cnt[k+1][r][i])>dp[l][r][i]){
dp[l][r][i]=Max[l][k-1][i]+Max[k+1][r][i]+vec[i-1]*(cnt[l][r][i]-cnt[l][k-1][i]-cnt[k+1][r][i]);
pos[l][r][i]=k;
}//Update Max and pre:
if(!dp[l][r][i])pos[l][r][i]=l;
if(dp[l][r][i]>Max[l][r][i+1]){
Max[l][r][i]=dp[l][r][i];
pre[l][r][i]=i;
}else{Max[l][r][i]=Max[l][r][i+1];pre[l][r][i]=pre[l][r][i+1];}
}
}
求方案的代码：
void dfs(int l,int r,int k){
if(l>r)return;
if(l==r){ans[l]=vec[k-1];return;}
ans[pos[l][r][k]]=vec[k-1];//满足点的值就是区间最小值
dfs(l,pos[l][r][k]-1,pre[l][pos[l][r][k]-1][k]);
dfs(pos[l][r][k]+1,r,pre[pos[l][r][k]+1][r][k]);
return;
}
时间复杂度 \(O(n^3m)\) 。
\(Part\) \(2.5.3\) ：更深层的东西
其实进一步思考一下我们会发现，在第一道题中我们一个区间 \(l\) ~ \(r\) 决策过程中的满足点的二元组是 \((pos,t)\) ，\(pos\) 是位置，\(t\) 是被吃的时间，而在MYJ中，满足点的二元组是 \((pos,val)\) ，\(val\) 是点权，观察这两个二元组，每一个 \(pos\) 将原区间分成两部分 \(l\) ~ \(pos-1\) 和 \(pos+1\) ~ \(r\) ，而 \(t\) 是区间 \(l\) ~ \(r\) 中最大的一个，\(val\) 是区间 \(l\) ~ \(r\) 中最小的一个，第一维满足左边的比它小，右边的比它大，第二位满足了是这个集合中的最值……这本质上就是一颗笛卡尔树！
\(Part\) \(2.6\) ：方块消除
此类问题的最大特点：将一段区间考虑完之后，它前面的区间和后面的区间会并在一起。我曾一度不能理解 \(dp_{l,r}\) 这个状态不是定义上依然正确吗？为什么不能做呢？答案是：状态没什么问题，不过这个状态转移不了。考虑你在一段区间内进行决策时，还要在意后没有没有一段在等着我这段区间去一起操作，所以这类问题的决策通常有以下几种：
\(1\). 这一段区间自己搞自己的。
\(2\). 这一段区间给前面留着一部分。
\(3\). 这一段区间带着后面的一部分一起搞。
\(4\). 干掉这个区间内部的一段，让它后面留着的部分继续往前靠。
\(Part\) \(2.6.1\) ：方块消除
顺着我们上面的思路走，定义状态 \(dp_{l,r,num}\) 表示我们去消除区间 \(l\) ~ \(r\) ，但是后面已经攒了 \(num\) 个与 \(r\) 同色的跟着的最大得分，考虑我们的几种决策：
\(1\). 直接将后面跟着的全部消除掉，得到的价值是 \(dp_{l,r-1,0}+(num+cnt_r)^2\) 。
\(2\). 找到一个 \(l\le k< r\) ，使得 \(col_k=col_r\) ，那么我们就可以先消除掉 \(k+1\) ~ \(r-1\) 这一段，攒更多的方块在前面一起消除，价值是 \(dp_{l,k,cnt_r+num}+dp_{k+1,r,0}\)
\(3\).如果区间长度为 \(1\) ，那就没得选了，直接连着后面攒的一起消除了，价值是 \((cnt_r+num)^2\) 。
时间复杂度 \(O(n^4)\) 的高效代码：
int DP(int l,int r,int res){
if(dp[l][r][res]!=-1)return dp[l][r][res];
if(l==r)return dp[l][r][res]=(num[r]+res)*(num[r]+res);
dp[l][r][res]=DP(l,r-1,0)+(num[r]+res)*(num[r]+res);
for(int k=l;k<r;++k)if(col[k]==col[r])
dp[l][r][res]=max(dp[l][r][res],DP(l,k,num[r]+res)+DP(k+1,r-1,0));
return dp[l][r][res];
}
\(Part\) \(2.6.2\) ：成绩单
首先看到 \(w_i\le 1000\) 但是 \(n\le 50\) ，所以直接离散化！
跟上一道题差不多，不过我们这次需要同时关心后面攒的成绩单的分数最大值 \(ma\) 和最小值 \(mi\) ，所以直接 \(dp_{l,r,ma,mi}\) 四维状态，预处理一下区间最大最小值，转移起来跟上面基本一致，时间复杂度 \(O(n^5)\) ：
int DP(int l,int r,int ma,int mi){
if(dp[l][r][ma][mi]!=-1)return dp[l][r][ma][mi];
if(l==r)return dp[l][r][ma][mi]=a+b*js(vec[max(w[l],ma)-1]-vec[min(w[l],mi)-1]);
dp[l][r][ma][mi]=
min(a+b*js(vec[max(Max[l][r],ma)-1]-vec[min(Min[l][r],mi)-1]),DP(l,r-1,max(ma,w[r]),min(mi,w[r])));
for(int k=l;k<r;++k)dp[l][r][ma][mi]=min(dp[l][r][ma][mi],DP(l,k,ma,mi)+DP(k+1,r,0,Up));
return dp[l][r][ma][mi];
}
\(Part\) \(2.7\) ：小结
最开始见到区间dp：这都什么神仙题啊？怎么都是没见过的怪东西啊?
做了很多题之后：欸，怎么又是跟上一道题同样的套路啊？
区间dp实际上就是很多种处理区间类dp的套路的整合，主要是要发现题目中区间的性质，然后对应到一个套路上。
当然区间dp的套路还有很多，不过我还没全部见识到。
标签：le,int,pos,Part,DP,区间,dp From： https://www.cnblogs.com/LzjNotFound/p/16855730.html