单调队列

单调队列优化dp

形如dp[i]=max/min (f[k]) + g[i]

//单调队列区间长度为k
long long que(int i){//让返回值尽量的大，队列单调减，使首元素恒最大 
    d[i]=dp[i-1]-sum[i];
    while(head<=tail&&d[q[tail]]<d[i])tail--;
    q[++tail]=i;
    while(head<=tail&&q[head]<i-k)head++;
    return d[q[head]];
}

滚动数组

dp[2][j][k]

int x=i&1;
dp[x][j][k] = dp[x ^ 1][j][k];

4