最近做CF的时候遇到单调队列优化DP的问题，看了一下网上这种题也很少，而且都很难理解，下面是两个解释的比较好的博客：
单调队列优化DP的基本思路：点击打开链接
两道例题详解：点击打开链接
下面讲一下我自己对单调队列优化dp的理解，首先不是所有dp都可以使用单调队列优化的，只有形如 dp[i]=max/min (f[k]) + g[i] （k<i && g[i]是与k无关的变量）才能用到单调队列进行优化。单调队列的作用就是：因为k与i相关，所以我们只要迭代一次i的同时，用单调队列保存f[k]的最值即可，这样就可以降低一维的复杂度。
还是挺难理解的，现在水平可能不够吧，还是多做题。
HDU3401代码：
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 2005;
const int INF = 1 << 30;
int n, maxp, w;
int ap[maxn], bp[maxn], as[maxn], bs[maxn], dp[maxn][maxn];
struct node
{int num;int val;node(int tnum = 0,int tval = 0) :num(tnum), val(tval) {}
};
deque<node> q;int main()
{int t,i,j,k;scanf("%d", &t);while (t--){scanf("%d%d%d", &n, &maxp, &w);for (int i = 1; i <= n; i++){scanf("%d%d%d%d", &ap[i], &bp[i], &as[i], &bs[i]);}for (i = 0; i <= n; i++)for (j = 0; j <= maxp; j++)dp[i][j] = -INF;for (i = 1; i <= w + 1; i++)//前w+1天只能买入for (j = 0; j <= min(maxp, as[i]); j++)dp[i][j] = -j*ap[i];dp[0][0] = 0;for (i = 1; i <= n; i++){for (j = 0; j <= maxp; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j]);//不买也不卖if (i <= w + 1) continue;int bf = i - w - 1;q.clear();for (j = 0; j <= maxp; j++)//处理买入{int nowf = dp[bf][j] + j*ap[i];//队列维护这个最大值while (!q.empty() && q.back().val < nowf)//将这个值插入队列，队列单调递减q.pop_back();q.push_back(node(j, nowf));while (!q.empty() && j - q.front().num > as[i])q.pop_front();dp[i][j] = max(dp[i][j], q.front().val - j*ap[i]);}q.clear();for (j = maxp; j >=0; j--)//处理卖出,注意因为是卖出，所以从大到小计算{int nowf = dp[bf][j] + j*bp[i];while (!q.empty() && q.back().val < nowf)q.pop_back();q.push_back(node(j, nowf));while (!q.empty() && q.front().num - j > bs[i])//从大到小确保q.front().num>jq.pop_front();dp[i][j] = max(dp[i][j], q.front().val - j*bp[i]);}}int ans = 0;for (i = 0; i <= maxp; i++){ans = max(ans, dp[n][i]);}printf("%d\n", ans);}return 0;
}