单调队列优化dp

刷题记录哦（by能力提升综合题单

多重背包

我们考虑，普通的多重背包是什么样子的

$f[j] = max(f[j-v[i]*k]+w[i]*k)(k\le num[i])$

我们考虑一下，平常在使用单调队列的时候，这个max

把max里面的所有的数都放进一个单调队列中，这显然是可以办到的，只需要开 $v[i]$ 个单调队列就好了，维护 $j\mod v[i]$ 的答案就好了（如果真的要听详细的讲解你并不应该来这里

P2216

由于a,b比较小，我们可以维护出来每一个n*n的正方形的最大值和最小值

那么我们考虑怎么维护：

对于每一行来说，我们求出它的所有的长度为n的子串的最大最小值，因为我们会发现，所有的n*n的正方形都可以分成n行，然后单独求之后合并，这n行如果单独当一个数字看的话（然后存成一列，也就相当于是求一个长度为n的子串了呀

然后考虑怎么求，简称：滑动窗口

P3089

我们先考虑暴力的dp怎么做（一个优化肯定要先考虑暴力啊

$f[i][j]$ 表示当前在第i个关键点，上一次从j跳过来，那么我们枚举 $f[j][k]$ 表示j上一次从k跳过来（因为一定要保证那个这一步小于等于上一步的条件

然后列出转移方程：

$f[i][j] = max(f[j][k]+a[i])(0\le j<i)(0\le k<j)(dis(j,k)\le dis(j,i))$

然后这个东西显然可以优化，我们枚举j的时候，把满足条件的k加进去再弹出来就好了（单调队列

P3572

我们考虑，如果说对于这么一个点i前面的点如果比他低，那么最多多1的贡献，如果比他高就不会多贡献

那么找到前面k个的贡献最小值，如果说这个最小值里面所有的高度都要比当前低，那么说明次小值一定大于最小值如果不加贡献也绝对不优

那么我们只考虑最小值，并且只考虑最小值中高度最高的一个位置

单调队列可以维护

P3522

这东西严格来说并不算是个dp

我们考虑，如果说这个位置可以和之前的区间连起来，那么说明这个位置的最高温度要比之前所有点的最低温度的最大值要高（意会

那么我们用单调队列维护每一个位置，如果说这个点的最高温度比较低，那么就把左边所有最低温度大于他的弹掉（那么他就是最高的温度了，然后这个点可以用最低温度向前弹（因为我们是需要维护单调的

然后就会发现，好耶！（~~过不了样例~~

因为如果一个最低温度要特别特别高把前面的弹掉了，不证明前面的没用不能统计到答案里

那么我们每一次用最低温度弹的时候就可以把这个位置的id赋成弹掉的这个位置的id，然后单调队列的时候用i减去队头的id就是答案，然后取max

P4544

这个题就不细讲了因为不难

$f[i][j]$ 表示当前在第i个点，并且已经带上了j吨饲料

那么转移的时候，可以并不在这个点买，也可以买，但是有存货限制（这个地方用单调队列

P1973

这个题好难哦

我们考虑第一问， $f[i][j]$ 表示i时间（离散化）一个会场j个活动另一个会场多少个活动

我们枚举一个区间使得这个区间里面的所有的活动都要选上然后转移

考虑如果一个活动必须要选怎么办捏

这个活动是有一个区间的，我们做出前缀dp数组和后缀dp数组

然后考虑合并一下下

这个区间两边的进行合并，枚举左右两边第一个会场选了多少个(强制这个区间里面的所有都给第二个会场就好啦)(反正都要枚举的)

然后我们发现，并不是只有这个区间里的活动给了第二个会场就好了，这个左右端点会发生改变，因为跨过这个区间的活动肯定不止一个，所以还得枚举左右端点

但是复杂度过不去

然后我们预处理出来 $ans[i][j]$ 表示i-j区间的答案

然后还是过不去

然后我们稍微加点优化就过了……比如……（看代码把

#include <bits/stdc++.h>
using namespace std;

const int maxn = 410;
const int inf = 0x3f3f3f3f;

int f[maxn][maxn], g[maxn][maxn];
int n;
int s[maxn], e[maxn], rk[maxn], tot;
int cnt[maxn][maxn];
int ans[maxn];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i] >> e[i], e[i] += s[i], rk[++tot] = s[i], rk[++tot] = e[i];
    sort(rk + 1, rk + 1 + tot);
    tot = unique(rk + 1, rk + 1 + tot) - rk - 1;
    for (int i = 1; i <= n; i++) {
        s[i] = lower_bound(rk + 1, rk + 1 + tot, s[i]) - rk;
        e[i] = lower_bound(rk + 1, rk + 1 + tot, e[i]) - rk;
    }
    //上述都是离散化的过程
    for (int i = 1; i <= tot; i++)
        for (int j = i + 1; j <= tot; j++)
            for (int k = 1; k <= n; k++)
                if (s[k] >= i && e[k] <= j)
                    cnt[i][j]++;
    //统计区间i-j之间有多少个活动
    memset(f, -0x3f, sizeof(f));
    memset(g, -0x3f, sizeof(g));
    for (int i = 1; i <= tot; i++)
        for (int j = 0; j <= n / 2; j++) {
            f[i][j] = -inf;
            if (j == 0)
                f[i][j] = cnt[1][i];
            for (int k = 1; k <= i - 1; k++) {
                f[i][j] = max(f[i][j], f[k][j] + cnt[k][i]);
                f[i][j] = max(f[i][j], f[k][max(0, j - cnt[k][i])]);
            }
        }
    //求出前缀f[i][j] 表示前i时间内j个活动之后另一个会场多少活动
    for (int i = tot; i >= 1; i--)
        for (int j = 0; j <= n / 2; j++) {
            g[i][j] = -inf;
            if (j == 0)
                g[i][j] = cnt[i][tot];
            for (int k = i + 1; k <= tot; k++) {
                g[i][j] = max(g[i][j], g[k][j] + cnt[i][k]);
                g[i][j] = max(g[i][j], g[k][max(0, j - cnt[i][k])]);
            }
        }
    //相当于是后缀的f数组
    for (int k = 1; k <= n; k++) {
        for (int i = s[k]; i >= 1; i--) {
            for (int j = e[k]; j <= tot; j++) {
                for (int l = 0; l <= cnt[1][i]; l++) {
                    for (int r = 0; r <= cnt[j][tot]; r++) {
                        ans[k] = max(ans[k], min(l + r + cnt[i][j], f[i][l] + g[j][r]));
                        if (g[j][r] < r)
                            break;
                        //我们只要让最小的两个加上cnt[i][j]而不是让大的加上，因为答案一定劣
                    }
                    if (f[i][l] < l)
                        break;//同理
                }
                if (cnt[1][i] + cnt[j][tot] < ans[k])
                    break;
                //如果说左边右边加起来都比ans[k]小了，那么肯定不优
                //考虑左右都给一个会场，中间不管给哪个会场都不会更新答案
                if (cnt[i][j] > cnt[1][i] + cnt[j][tot])
                    break;
                //如果中间的活动数目要比左右大了，那么肯定也更新不了答案了（看上面式子就好了，式子的右半边是左右两边有多少个活动，那么这些活动取min之后肯定是这个cnt[1][i]+cnt[j][tot]，那么说明接着搞这个和会变得越来越小，就没有意义了（无用
            }
        }
        ans[0] = max(ans[0], ans[k]);
    }
    for (int i = 0; i <= n; i++)
        cout << ans[i] << endl;
    return 0;
}

（不容易的放了一次代码）（我实在是懒了

P2569

这个还是比较简单的把，就是稍微分个类的事情

$f[i][j]$ 表示i天的时候手上j张邮票的赚钱最大数量

直接从头买
今天不买从昨天转移过来（其实这个就已经覆盖掉第一个了？但是还是加上吧因为题解有）（笑
今天买
今天卖

然后就是个经典的单调队列优化dp了呀

（我懒

P4852

话说为什么我做的这几个题感觉都挺简单的，挺套路的至少我觉得

$f[i][j]$ 表示当前在第i个位置，连抽了j次

然后转移，如果说在一个位置连抽的，那后边就单抽就好了