DP优化

单调队列优化

前置技能：单调队列（经典的问题模型：洛谷P1886 滑动窗口）

对于序列中的每个点，从其左侧一段决策区间内的最值进行转移，且决策区间随着序列下标的增大也不断右移（就像窗口向右滑动）。

设

于是，我们只要维护一个队列，满足下标递增，决策性递减。我们需要当前的队首成为最优决策点，那么当队首第一次超出了区间范围（以后也就永远超出了）就把它出队。为了保证单调性，队尾新加入点之前，要先把队列中比它劣的点依次从队尾出队。

题解：

两个单调队列一个最大一个最小

然后？

就可以了啊

1、维护队首（就是如果你已经是当前的m个之前那你就可以被删了,head++）

2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态）

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,m;
int q1[1000001],q2[1000001];
int a[1000001];
int min_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q1[h]+m<=i) h++;
        while(h<=t&&a[i]<a[q1[t]]) t--;
        q1[++t]=i;
        if(i>=m) printf("%d ",a[q1[h]]);
    }
    cout<<endl;
}
int max_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q2[h]+m<=i) h++;
        while(h<=t&&a[i]>a[q2[t]]) t--;
        q2[++t]=i;
        if(i>=m) printf("%d ",a[q2[h]]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    min_deque();
    max_deque();
    return 0;
}

View Code

前缀和优化

当DP过程中需要反复从一个求和式转移的话，可以先把它预处理一下。运算一般都要满足可减性。

比较简单就不展开了

洛谷P2513 [HAOI2009]逆序对数列

题解：

考虑i的放置,i为最大值,所以放在i-1个位置都可以计算出对答案的贡献

dp[i][j]=Σdp[i-1][k] (j-i+1 <=k<= j)

特别的到i时最多可以贡献i-1对逆序对，所以从dp[0]~dp[j-i+1]这一段不能加

n^3超时，可用前缀和优化

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1001
#define mod 10000
using namespace std;
int dp[N][N];
int n,k,ans,sum;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) dp[i][0]=1;
    for(int i=2;i<=n;i++)
    {
        sum=0;
        for(int j=0;j<=k;j++)
        {
            (sum+=dp[i-1][j])%mod;
            dp[i][j]=sum%mod;
            if(j-i+1>=0)((sum-=dp[i-1][j-i+1])+=mod)%mod;
        }
    }
    printf("%d
",dp[n][k]);
    return 0;
}

View Code

斜率优化

与决策单调性有着说不清的联系。

考虑两个决策

这时候根据题目特点把

下面第一题对两种理解斜率优化的方法做了更详细的分析（最好看第二种，因为第一种有针对性，不通用）

于是我们用数据结构维护凸壳上的所有点，具体实现依题而定。

不管是什么题，加入决策点的时候要保证斜率递增/递减。

如果

如果斜率

题解：

斜率优化DP入门题。

观察题目发现如果有两块土地

斜率优化，维护一个下凸包即可。

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

inline int read()
{
    int x=0; int f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1; ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

const int MAXN = 100005;
struct data {long long x,y;} a[MAXN];
long long x[MAXN],y[MAXN],f[MAXN],q[MAXN];
int n,tot;

inline bool cmp(data a,data b)
{return a.x==b.x?a.y<b.y:a.x<b.x;}

inline double slop(int a,int b)
{return (double)(f[b]-f[a])/(y[a+1]-y[b+1]);}

int main(int argc, char const *argv[])
{
    n=read();
    for(int i=1; i<=n; i++)
        a[i].x=read(),a[i].y=read();
    sort(a+1,a+n+1,cmp);
    for(int i=1; i<=n; i++)
    {
        while(tot && a[i].y>=y[tot]) tot--;
        x[++tot]=a[i].x; y[tot]=a[i].y;
    }
    int l=0,r=0;
    for(int i=1; i<=tot; i++)
    {
        while(l<r && slop(q[l],q[l+1])<x[i]) l++;
        int t=q[l]; f[i]=f[t]+y[t+1]*x[i];
        while(l<r && slop(q[r],i)<slop(q[r-1],q[r])) r--;
        q[++r]=i;
    }
    printf("%lld",f[tot]);
    return 0;
}

View Code

二分栈

我们使用决策二分栈（一种单调栈）来维护所有有用的决策，其中栈顶是当前最优决策。

为什么叫二分栈呢？

我们可以把

我们需要栈顶为当前的最优解。而如果栈中有不止一个元素，则可能存在一个

上面提到的这个可二分的性质就派上用场了。对于当前的