测试一下博客，乱发点东西 ## （转移）和结尾元素有关的dp ### 1、只最后一个元素相关 #### 问题1：最长上升连续子串（连续区间dp） 对于连续区间之间的$dp$，转移的对象极为清晰，不多赘述 设置$dp[i]$表示以$a[i]$为**右端点**的最长上升子串长度，如果$a[i]<=a[i-1]$则$dp[i]=0$，否则$dp[i]=dp[i-1]+1$ #### 问题2：（子序列dp） [Meeting Time II](http://10.7.95.2/CLanguage/contests/1177/problems/1003.html) 二维平面上有n个站点，你需要按顺序经过（从站点1到站点2到站点3...）这些站点，但你可以选择k个站点进行跳过，求最短路 设置$dp[i][j]$表示以$i$节点作为**右端点**且已经跳跃了$j$次的最短路，这样就可以通过枚举上一个节点$O(n^3)$转移 （扯开去讲一下，因为区间之间的转移和**最后一个元素**是什么有关，所以对于每一个转移知道状态的结尾元素，设置以$i$作为**右端点**是非常有必要的，如果这边状态中$i$含义是前$i$个的话就没办法转移了，因为对于$dp[i][1]$你不知道跳过了哪个节点。但有的时候对于**子序列计数问题**，我们会将状态设置为前$i$个的数量前缀和，因为这个时候就我们不需要知道最后一个元素具体位置，只需要知道某结尾序列数量即可） #### 问题3、最长上升子序列（子序列dp的优化） 同样是寻找上一个端点，不同于$O(n)$暴力的寻找，在$LIS$里面我们通过二分优化了寻找上一个元素的时间复杂度 ### 2、只和最后k个元素相关 考虑状压最后$k$个元素的形态，花$O(2^k)$的复杂度进行转移 ### 3、只和最后一个连续段长度相关，且间隔(gap)固定 （间隔不定的话就只能二进制枚举了） 总体来讲思路都是极为相似的，通过设置$dp$状态为右端点来进行转移 设置$dp[i][j]$为以$i$作为右端点的，最后一个连续段长度为$j$的$dp$值，考虑转移 $$ dp[i+gap+k][k]=f(dp[i][j],k) $$ ## 前缀和优化dp [Armchairs](https://codeforces.com/contest/1525/problem/D) 题目的意思是有$n$个座位$m$个人$（m<n/2）$坐在一些位置上，现在要求原来这些坐着人的位置都空出来，让这些人坐在其他座位上，问移动距离总和的最小值。 设$dp[i][j]$表示第i个人坐到第j个原来空着的位置，并且前i个人完全匹配的最小移动距离。 我们来考虑转移 $$ dp[i][j]=min_{k=1,2,..,j-1}(dp[i-1][k])+abs(dis1[i]-dis0[j]) $$ 我们想到了一个O(n^3)的dp，然后我们发现$min_{k=1,2,..,j-1}(dp[i-1][k])$ 是可以$O(n)$预处理的，那么这个$dp$就被优化掉了一维，变成了$O(n^2)$ [Matrix ](https://ac.nowcoder.com/acm/contest/12986/K) 题目的意思是在这个矩阵里面选取一块楼梯形的区域，使得区域和最大。 我们设状态$dp[i][j][k]$，$i$表示第$i$列，$j$表示第$j$列的高度，$k$表示总总共选取的方格数。 考虑转移 $$ dp[i][j][k]=max_{t>=j}(dp[i-1][t][k-j]) $$ 复杂度为$O(n^4)$ 然后我们发现这个$max$值满足递推关系 $$max_{t>=j+1}(dp[i-1][t][k-j])=max(max_{t>=j}(dp[i-1][t][k-j]),dp[i-1][j][k-j])$$ 所以我们对于每列可以预处理出$max$值，从而优化复杂度至$O(n^3)$ 其实这种优化$dp$的思想是极为自然的，对于 ```cpp for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)dp(i,j)=max(f(i,j)+g(k)); ``` 这样的式子，我们自然会想到把$g(k)$预处理出来重复使用，优化掉一维。 ## 单调队列优化dp [[SCOI2010]股票交易](https://www.luogu.com.cn/problem/P2569) 首先$O(n^3)$复杂度的$dp$是容易想到的，现在对其进行优化 设$dp[i][j]$表示前$i$天拥有$j$股的最大收益 $$ dp[i][j]=MAX_{(t=0,1,...,bs[i])}(dp[i-w][j+t]+t*bp[i])\\ =MAX_{(t=0,1,...,bs[i])}(dp[i-w][j+t]+(j+t)*bp[i])-j*bp[i] $$ 这样处理之后**括号内的值和$j$无关**，虽然看上去是$j+t$，但事实上相当于求 $$ MAX_{(t=j+t,...,j+t+bs[i])}(dp[k][t]+t*C)\\=MAX_{(t=a,...,a+c)}f(t) $$ 问题就和滑动窗口等价了 复杂度降至$O(n^2)$ ## 斜率优化dp 对于形如$dp[i]=min_{j<i}(dp[j]+f[i]*g[j])$的转移方程，如果$g[j]$满足单调性我们可以通过维护凸包来$O(1)$求出$dp[i]$ 方法如下，移项得$dp[i]-f[i]g[j]=dp[j]$，把可以看作斜率为$-f[i]$的直线在$(j<i)$的点$(g[j],dp[j])$中取得的最小截距，维护一个上/下凸包即可 [例题1:](http://10.7.95.2/CLanguage/showproblem?problem_id=1274) [例题2:](http://10.7.95.2/CLanguage/showproblem?problem_id=1267) [例题3:](http://10.7.95.2/CLanguage/showproblem?problem_id=1239) 简易板子 ```cpp #include<bits/stdc++.h> using namespace std; long long A[5000005]; int Queue[5000005]; long long dp[1000005]; int n,L; double slope(int a,int b) { return (((double)dp[a]+A[a]*A[a]+L)-((double)dp[b]+A[b]*A[b]+L))/(A[a]-A[b]); } int main() { scanf("%d%d",&n,&L); long long sum=0; for(int i=1;i<=n;i++) { int temp; scanf("%d",&temp); sum+=temp; A[i]=sum; } int head=1,tail=1; for(int i=1;i<=n;i++) { while(head<tail&&slope(Queue[head],Queue[head+1])<2*A[i])head++; dp[i]=dp[Queue[head]]+(A[i]-A[Queue[head]])*(A[i]-A[Queue[head]])+L; while(head<tail&&slope(Queue[tail],Queue[tail-1])>slope(i,Queue[tail-1]))tail--; Queue[++tail]=i; } printf("%lld\n",dp[n]); return 0; } ``` ## 平行四边形优化dp 一般就是证明$w(l-1,r)+w(l,r+1)\le w(l,r)+w(l-1,r+1)$ 然后利用决策单调性优化即可，习题很多，一般如果和区间长度有关的权值都可以尝试证明这个不等式