HDU 4374 단일 대기열 최적화 DP

이 문제의 이동은 매우 뚜렷하다.
dp[i][j]로 i층 j 위치에 도달했을 때의 최대 득점을 표시하다
sum[i][j]는 i층 앞 j 개수의 합을 나타낸다
dp[i][j] = max(max(dp[i - 1][j + k] + sum[i-1][j +k-1] - sum[i - 1][j - 1] + score[i][j]), max(dp[i - 1][j - k] - sum[i-1][j -k] + sum[i - 1][j] + score[i][j]))
   t >= k >= 0
그리고 그중에 k와 무관한 것을 꺼내라.나머지 부분은 층마다 처리할 수 있는 것을 발견할 수 있을 때 가장 큰 값을 구할 수 있다
왼쪽 t의 구간과 오른쪽 t의 구간으로 나눌 수 있다
두 개의 단조로운 대열을 유지하면 된다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 105
#define MAXM 11111
#define INF 1000000000
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int n, m, x, t;
int in()
{
    int flag = 1;
    char ch;
    int a = 0;
    while((ch = getchar()) == ' ' || ch == '
');
    if(ch == '-') flag = -1;
    else
    a += ch - '0';
    while((ch = getchar()) != ' ' && ch != '
')
    {
        a *= 10;
        a += ch - '0';
    }
    return flag * a;
}
int dp[MAXN][MAXM];
int sum[MAXN][MAXM];
int lmx[4 * MAXM];
int rmx[4 * MAXM];
int a[MAXN][MAXM];
int q[MAXM];
int main()
{
    while(scanf("%d%d%d%d", &n, &m, &x, &t) != EOF)
    {
        for(int i = 1; i <= n + 2; i++)
            for(int j = 1; j <= m; j++)
                sum[i][j] = 0, dp[i][j] = -INF, a[i][j] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                a[i][j] = in();
                sum[i][j] = sum[i][j - 1] + a[i][j];
            }
        int tmp = 0;
        for(int i = x; i <= x + t; i++)
        {
            tmp += a[1][i];
            dp[1][i] = tmp;
            dp[2][i] = dp[1][i] + a[2][i];
        }
        tmp = 0;
        for(int i = x; i >= x - t; i--)
        {
            tmp += a[1][i];
            dp[1][i] = tmp;
            dp[2][i] = dp[1][i] + a[2][i];
        }
        for(int i = 3; i <= n + 1; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                lmx[j] = dp[i - 1][j] - sum[i - 1][j];
                rmx[j] = dp[i - 1][j] + sum[i - 1][j - 1];
            }
            int head = 1, rear = 0;
            for(int j = 1; j <= m; j++)
            {
                while(head <= rear && lmx[q[rear]] <= lmx[j]) rear--;
                q[++rear] = j;
                while(head <= rear && q[head] < j - t) head++;
                dp[i][j] = max(lmx[q[head]] + sum[i - 1][j] + a[i][j], dp[i][j]);
            }
            head = 1, rear = 0;
            for(int j = m; j >= 1; j--)
            {
                while(head <= rear && rmx[q[rear]] <= rmx[j]) rear--;
                q[++rear] = j;
                while(head <= rear && q[head] > j + t) head++;
                dp[i][j] = max(rmx[q[head]] - sum[i - 1][j - 1] + a[i][j], dp[i][j]);
            }
        }
        int ans = -INF;
        for(int i = 1; i <= m; i++)
            if(dp[n + 1][i] > ans) ans = dp[n + 1][i];
        printf("%d
", ans);
    }
    return 0;
}