湖南附中模拟day1 金坷垃

题意描述
“没有金坷垃，怎么种庄稼？”
花花家有一块田，所有庄稼排成了 N 行 M 列。初始时，每棵庄稼都有一个自己的高度
hi;j。花花每次可以使用 1mol 的金克拉使一棵庄稼的高度增加 1。现在有 Q 个询问，花花每
次想知道最少需要使用多少 mol 的金克拉，才能使田里出现一块高度一致，大小为 ai × bi 的
庄稼。
其中每个询问是独立的，也就是说这次询问使用的金克拉不会影响到下一次询问。
输入格式
输入第一行包含两个正整数 N 和 M。
接下来 N 行每行包括 M 个正整数，表示每棵庄稼最初的高度 hi;j。
接下来 Q 行每行包括两个正整数 ai 和 bi。
输出格式
输出共包括 Q 行，对于每个询问输出使用金克拉的最少 mol 数。
样例输入
3 4
1 8 3 4
5 2 3 1
3 6 2 2
4
1 1
2 2
2 3
3 2
样例输出
0 4
15
9

样例解释
对于第二个询问，最优方案之一为选择以下庄稼：
3 1
2 2
对于第三个询问，最优方案之一为选择以下庄稼：
5 2 3
3 6 2
对于第四个询问，最优方案之一为选择以下庄稼：
3 4
3 1
2 2
3.7 数据规模与约定
• 对于 50% 的数据： N; M ≤ 40；
• 另有 20% 的数据： N; M ≤ 200；
• 另有 20% 的数据： N; M ≤ 300；
• 对于 100% 的数据： N; M; hi;j ≤ 1000; Q ≤ 50; 1 ≤ ai ≤ N; 1 ≤ bi ≤ M。

/*

分析题目，当一块农田的位置被确定下来之后，求出其中最高的一亩田，其他的就一定要变成和他相同的高度，问题就是这个最大值不好求，我们想到了滑动窗口这个典型例题，这个求最大值的过程可以看做是一个二维的“滑动窗口”，这样先处理每一行，在处理矩阵，分别使用两次单调队列

*/

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = ;

const int inf = ;

int n,m,qes,h[maxn][maxn];

int q[maxn],l,r,cnt,qc[maxn],mc[maxn][maxn];

ll mx[maxn][maxn],sum[maxn][maxn];

int read(){

    char ch=getchar();

    int x=,f=;

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};

    return x*f;

}

void update(int &x,int y){

    if(y > x) x = y;

}

void clean(){

    l = ;

    r = ;

    q[] = inf;

    q[] = -inf;

    cnt = ;

}

void push(int x,int lm){

    q[++r] = x;

    qc[r] = ;

    q[r+] = -inf;

    while(q[r] >= q[r-]){

        qc[r-] += qc[r];

        q[r-] = q[r];

        q[r--] = -inf;

    }

    if(++cnt > lm){

        if(--qc[l] == ) q[l++] = inf;

    }

}

void work(int y,int x){

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

        clean();

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

            push(h[i][j],x);

            mx[i][j] = q[l];

        }

    }

    ll ans = 9876543210123LL;

    ll base = y*x;

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

        clean();

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

            push(mx[i][j],y);

            if(i >= y) ans = min(ans,base * q[l] - (sum[i][j] - sum[i-y][j] - sum[i][j-x] + sum[i-y][j-x]));

        }

    }

    cout<<ans<<endl;

}

void input(){

    freopen("fertilize.in","r",stdin);

    freopen("fertilize.out","w",stdout);

    n = read();

    m = read();

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

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

            h[i][j] = read();

            sum[i][j] = sum[i][j-] + h[i][j];

        }

    }

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

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

            sum[i][j] = sum[i-][j] + sum[i][j];

        }

    }

    qes = read();

    int y,x;

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

        y = read();

        x = read();

        work(y,x);

    }

}

int main(){

    input();

    return ;

}

巴特西

湖南附中模拟day1 金坷垃

最新文章

热门文章