bzoj 1855 dp + 单调队列优化

思路：很容易写出dp方程，很容易看出能用单调队列优化。。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define y1 skldjfskldjg

#define y2 skldfjsklejg

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

int n, m, w, ap[N], bp[N], as[N], bs[N], dp[N][N];

int stk[N], head, rear;

int cal1(int p, int i, int x) {

    return dp[p][x] + x * ap[i];

}

int cal2(int p, int i, int x) {

    return dp[p][x] + x * bp[i];

}

int main() {

    scanf("%d%d%d", &n, &m, &w);

    for(int i = ; i <= n; i++)

        scanf("%d%d%d%d", &ap[i], &bp[i], &as[i], &bs[i]);

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++)

            dp[i][j] = -inf;

    dp[][] = ;

    int ans = ;

    for(int i = ; i <= n; i++) {

        head = , rear = ;

        int p = max(, i - w - );

        for(int j = ; j <= m; j++) dp[i][j] = dp[i - ][j];

        for(int j = ; j <= m; j++) {

            while(rear >= head && cal1(p, i, j) > cal1(p, i, stk[rear])) rear--;

            stk[++rear] = j;

            while(j - as[i] > stk[head]) head++;

            dp[i][j] = max(dp[i][j], cal1(p, i, stk[head]) - j * ap[i]);

        }

        head = , rear = ;

        for(int j = m; j >= ; j--) {

            while(rear >= head && cal2(p, i, j) > cal2(p, i, stk[rear])) rear--;

            stk[++rear] = j;

            while(j + bs[i] < stk[head]) head++;

            dp[i][j] = max(dp[i][j], cal2(p, i, stk[head]) - j * bp[i]);

            ans = max(ans, dp[i][j]);

        }

    }

    printf("%d\n", ans);

    return ;

}

/*

*/