可以用队列优化或斜率优化的dp这一类的问题为 1D/1D一类问题
即状态数是O(n)，决策数也是O(n)
单调队列优化
我们来看这样一个问题：一个含有n项的数列(n<=2000000)，求出每一项前面的第m个数到它这个区间内的最小值
可以使用RMQ求区间最小值，那么时间复杂度是O(nlogn)，不是让人很满意。
dp[i]为i-m+1->i这个区间的最小值。
那么状态转移方程是
可以看出，这个题目的状态数是O(n)，决策数是O(m)，且决策的区间是连续的，那么可以尝试想办法把O(m)优化成O(1)
我们可以用单调队列维护一个数据结构，这个数据结构有两个域，pos和val，pos代表下标，val代表该下标所对应的值。队列中的pos单调递增，且val也单调递增
那么当计算一个状态时，只要从队首不断弹出pos<i-m+1的数据，只要pos>=i-m+1,那么该决策就是最优的，因为队列是单调的啊。
同理，同队尾插入一个数据时，只要不断剔除val比a[i]大的数据，直到遇到小于它的，然后将该数据插入队尾。
每个数据只入队列，出队列一次，所以时间复杂度是O(n)，
分析：为什么插入的时候，比a[i]大的数据可以剔除，因为j<i时，a[j] > a[i], 那么以后所有的决策中，a[i]都比a[j]更优
为什么可以不断删除pos<i-m+1的数据，因为i是递增的，该数据对当前的i没用，那么对以后的i也是没用的。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
*/
const int N = + ;
int a[N];
int dp[N];
int q[N], head, tail;
int main()
{
int n, m;
while (scanf("%d%d", &n,&m) != EOF)
{
for (int i = ; i <= n; ++i)
scanf("%d", &a[i]);
head = tail = ;
q[tail++] = ;
dp[] = a[];
for (int i = ; i <= n; ++i)
{
while (head < tail && a[i] < a[q[tail - ]])//插入新的元素，要使得队列依旧单调递增
tail--;
q[tail++] = i;
while (head < tail && q[head] < i - m + )//剔除不合要求的pos
head++;
dp[i] = a[q[head]];
}
for (int i = ; i <= n; ++i)
printf("%d ", dp[i]);
puts("");
/*
5 3
1 2 3 4 5
1 1 1 2 3
*/
}
return ;
}
那么我们可以抽象出一类模型
需要注意到，上面要求可选的决策集是连续的。同时也可以注意到，当前决策所需要的值是不受现在的状态所影响的，即g(i)与w[x]是相互独立的。
斜率优化
我们在单调队列的最后说道，当前决策所需要的值是不受现在的状态所影响的，即g(i)与w[x]是相互独立的。
还有的1D/1D一类问题是想下面这样的。
但是如果状态转移方程是这样的： dp[i]=dp[j]+(x[i]-x[j])*(x[i]-x[j]) ，1<=j<=i 把括号化开后，得到2x[i]*x[j], 这使得当前决策所需要的值受当前状态的影响
所以上面单调队列的方法就不行了。
题目有n个字符要打印，连续打印k个字符的代价是(c1+c2+...+ck)^2 + m, m是题目所给的常量
题目要优化的是，如果连续打印过多，那么代价平方之后就会很大，如果连续打印过少，那么就多加几次m。
dp[i]表示打印第i个字符时的最小花费
dp[i] = min(dp[i],dp[j] + (sum[i]-sum[j])^2+m) 1<=j<i
那么复杂度是O(n^2),是无法接受的。
那么就需要优化了,
当j > k 且j比k优的时候
dp[j] + (sum[i]-sum[j])^2 + m < dp[k] + (sum[i]-sum[k])^2+m
化简得(dp[j]+sum[j]^2 - (dp[k]+sum[k])^2 )/ (2sum[j]-2sum[k]) < sum[i]
这就很像斜率表达式了，而且这个斜率表达式小于另一个斜率，即sum[i]。
从下图我们可以看出，当j为k优时，斜率为sum[i]的斜线过j点与y轴的截距更小。
令g[j,k]表示上面的式子
当k<j<i时，且g[i,j] <= g[j,k]时，j是可舍弃的。
如果所示，假设j成为最优，那么必须有sum[i] > g[j,k], 且 sum[i] < g[i,j], 即 g[j,k] < sum[i] < g[i,j], 也即有g[i,j] > g[j,k],但是与前提条件g[i,j] <= g[j,k]矛盾，所以假设不成立，所以j是可以舍弃的。
所以，我们要维护一个下凸的图形（即斜率不断增大），因为横坐标（也就是sum[j]）是递增的，所以用一个队列维护就行了。如果横坐标不递增的话，就要用平衡树了。
如果，是一个下凸包，我们只要判断sum[i]所代表的斜线与哪个点在y轴上的截距最小就行了，又因为sum[i]是递增的，所以前面判断过的点不用再次判断。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
const int INF = <<;
/*
普通的dp需要遍历以前的所有值，
斜率dp就是通过舍弃一些值，必须是当前可舍弃，以后也是可舍弃的值，从而减少遍历量
或者是使得队首的元素就是最优的， 关键是如何判断可舍弃，。。。。。通过数学分析斜率来舍弃？？？ 第i个字符肯定接在前面j个字符的后面，或者另起一行，但是费用该怎么算呢
dp[i][1]表示1另起一行 ，那么费用是 dp[i][1] = ci^2 + m + min(dp[i-1][0],dp[i-1][1])
dp[i][0] 表示接在前面j个字符的后面的最小费用 sum{cost[j]}^2+m + min(dp[j-1][0],dp[j-1][1]) */ const int N = + ;
int sum[N];
int dp[N];
int q[N], head, tail;
int getUp(int i, int j)
{
return dp[i] + sum[i] * sum[i] - (dp[j] + sum[j] * sum[j]);
}
int getDown(int i, int j)
{
return * sum[i] - * sum[j];
}
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= n; ++i)
{
scanf("%d", &sum[i]);
sum[i] += sum[i - ];
}
head = tail = ;
q[tail++] = ;
for (int i = ; i <= n; ++i)
{
/* */
while (head + < tail && getUp(q[head + ], q[head]) <= sum[i] * getDown(q[head + ], q[head ]))
head++;
dp[i] = (sum[i] - sum[q[head]]) * (sum[i] - sum[q[head]]) + m + dp[q[head]];
while (head + < tail && getUp(i, q[tail - ])*getDown(q[tail - ], q[tail - ]) <= getUp(q[tail - ], q[tail - ])*getDown(i, q[tail - ]))
tail--;
q[tail++] = i;
}
printf("%d\n", dp[n]);
}
return ;
}
总结，
当横坐标递增，斜率递增时，用队列维护，可以在O(1)的时间内找到最优值，就是上面的情况。
当横坐标递增，斜率不递增时，我们可以二分，因为凸包的斜率是递增的，所以可以二分。
当横坐标不递增时，用平衡树维护。
【参考文献】
《1D1D动态规划优化初步》 作者：南京师范大学附属中学 汪一宁
《用单调性优化动态规划》 JSOI2009集训队论文