poj2019

dp

利用单调双向队列。类似sliding windows。

View Code
#include <iostream>
#include
<cstdio>
#include
<cstdlib>
#include
<cstring>
using namespace std;

#define maxn 260

struct Node
{
int pos, a;
Node()
{
}
Node(
int pp, int aa) :
pos(pp), a(aa)
{
}
} q[maxn];

int n, sub, m;
int f[maxn][maxn], fmax[maxn][maxn], fmin[maxn][maxn];
int lmax[maxn][maxn], lmin[maxn][maxn];
int front, rear;

int ins1(Node x)
{
while (front < rear && x.pos - q[front].pos >= sub)
front
++;
while (front < rear && x.a > q[rear - 1].a)
rear
--;
q[rear
++] = x;
return q[front].a;
}

int ins2(Node x)
{
while (front < rear && x.pos - q[front].pos >= sub)
front
++;
while (front < rear && x.a < q[rear - 1].a)
rear
--;
q[rear
++] = x;
return q[front].a;
}

void input()
{
scanf(
"%d%d%d", &n, &sub, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf(
"%d", &f[i][j]);
}

void work()
{
for (int i = 0; i < n; i++)
{
front
= rear = 0;
for (int j = 0; j < sub - 1; j++)
ins1(Node(j, f[i][j]));
for (int j = sub - 1; j < n; j++)
lmax[i][j]
= ins1(Node(j, f[i][j]));
}
for (int i = sub - 1; i < n; i++)
{
front
= rear = 0;
for (int j = 0; j < sub - 1; j++)
ins1(Node(j, lmax[j][i]));
for (int j = sub - 1; j < n; j++)
fmax[j][i]
= ins1(Node(j, lmax[j][i]));
}

for (int i = 0; i < n; i++)
{
front
= rear = 0;
for (int j = 0; j < sub - 1; j++)
ins2(Node(j, f[i][j]));
for (int j = sub - 1; j < n; j++)
lmin[i][j]
= ins2(Node(j, f[i][j]));
}
for (int i = sub - 1; i < n; i++)
{
front
= rear = 0;
for (int j = 0; j < sub - 1; j++)
ins2(Node(j, lmin[j][i]));
for (int j = sub - 1; j < n; j++)
fmin[j][i]
= ins2(Node(j, lmin[j][i]));
}

}

int main()
{
//freopen("t.txt", "r", stdin);
input();
work();
for (int i = 0; i < m; i++)
{
int a, b;
scanf(
"%d %d", &a, &b);
a
= a + sub - 2;
b
= b + sub - 2;
printf(
"%d\n", fmax[a][b] - fmin[a][b]);
}
return 0;
}
原文地址:https://www.cnblogs.com/rainydays/p/2114970.html