文档章节

胡策DAY2

Loi_DL
 Loi_DL
发布于 2016/11/03 07:41
字数 1048
阅读 9
收藏 0

施肥
【问题描述】
学校里有一块田地,所有庄稼排成了 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 4
3 1
2 2
【数据说明】
对于 30%的数据 1≤n,m≤30
对于 50%的数据 1≤n,m≤300
对于 100%的数据 1≤n,m,hi,j≤1000 1≤ai≤n 1≤bi≤m 1≤Q≤30
题解:这个题吧怎么做很好想,可是怎么降低时间复杂度是个问题。找一遍每个符合啊ai*bi的田地求最少需要多少化肥。那么需要先知道这个块田地的最大值是什么,所有的和是什么。数据范围1000,需要n2的算法,所以最大值得O(n)求,可以维护一个二维前缀和。O(n)怎么求呢。二维?No No No 不用,可以先处理行在处理列,两边一维解决,接下来就是怎么O(n)求。我们可以维护一个单调递减队列,正确性(lc说显然)。然后问题就解决了O(∩_∩)O~~。
(O(n)求最值可以去做poj滑动窗口 or codves窗口)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
void read(int &a)
{
    a=0;
    char c=getchar();
    while(c<'0'||c>'9')
    c=getchar();
    while(c>='0'&&c<='9')
    {
        a*=10;
        a+=c-'0';
        c=getchar();
    }
}
const int lc=1006;
int num[lc][lc],S[lc][lc],sum[lc][lc],mx[lc][lc];
int a,b,n,m,H,T,Q;
int q[lc];
void qzh()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            read(num[i][j]);
            S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+num[i][j];
        }
    return ;
}
void xw()
{
    while(Q--)
    {
        read(a);read(b);
        if(a==1&&b==1)
        {
            puts("0");
            continue;
        }
        int ans=1e9+7;
        for(int i=a;i<=n;i++)
            for(int j=b;j<=m;j++)
            sum[i][j]=S[i][j]-S[i-a][j]-S[i][j-b]+S[i-a][j-b];
        for(int i=1;i<=m;i++)
        {
            H=1,T=0;
            for(int j=1;j<=n;j++)
            {
                while (H<=T&&num[j][i]>num[q[T]][i]) T--;
                q[++T]=j;
                if(j>a)
                while (H<=T&&q[H]<=j-a) H++;
                mx[j][i]=num[q[H]][i];
            }
        }
        for(int i=a;i<=n;i++)
        {
            H=1,T=0;
            int Max=0;
            for(int j=1;j<=m;j++)
            {
                while (H<=T&&mx[i][j]>mx[i][q[T]]) T--;
                q[++T]=j;
                if(j>b)
                while (H<=T&&q[H]<=j-b) H++;
                Max=mx[i][q[H]];
                if(j>=b)
                ans=min(ans,Max*a*b-sum[i][j]);
            }
        }
        printf("%d\n",ans);
    }
    return;
}
void work()
{
    read(n);read(m);
    qzh();
    read(Q);
    xw();
    return ;
}
int main()
{
    //freopen("fertile.in","r",stdin);
    //freopen("fertile.out","w",stdout);
    work();
    return 0;
}

下面是30暴力。

#include <iostream>
#include <cstdio>
using namespace std;
int mp[1050][1050];
int n,m;
int q,a,b;
int zda(int x,int y)
{
    int maxx=-1;
    for(int i=x;i<=x+a-1;i++)
        for(int j=y;j<=y+b-1;j++)
        maxx=max(maxx,mp[i][j]);
    int ans=0;
    for(int i=x;i<=x+a-1;i++)
        for(int j=y;j<=y+b-1;j++)
        ans+=maxx-mp[i][j];
    return ans;
}
int main()
{
    //freopen("fertile.in","r",stdin);
    //freopen("fertile.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)   
        scanf("%d",&mp[i][j]);
    scanf("%d",&q);
    while (q!=0)
    {
        q--;
        int dan=1e9+7;
        scanf("%d%d",&a,&b);
        if(a==1&&b==1)
        printf("0\n");
        else 
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                {
                    if(i+a-1<=n&&j+b-1<=m)
                    dan=min(dan,zda(i,j));
                }
            printf("%d\n",dan);
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;

© 著作权归作者所有

下一篇: 10.18
Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
NOIP2017提高组玩挂

话说比赛时的电脑调试,有 恶心的问题,第一次输出中间结果好恶心。差点把我调吐了。 DAY1 第一题 小凯的疑惑 题目描述 小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小...

qq_35713030
2017/11/13
0
0
真便宜。买买买!

hello,我票贩子又来了,快上车: 知乎 Live - 全新的实时问答 我就不说通过这个live你能获得什么了,自己感悟吧。嘘 我们这次live请到了以下各位: 科大讯飞执行总裁 @胡郁 (胡郁,中国科学...

军师
2017/12/01
0
0
python攻关之字典详情

一、什么是字典 字典是python中的唯一的映射类型,采用键值对(key-value)的形式储存数据。 二、字典的特点 2.1 python对key进行哈希函数运算,根据计算的结果决定value的存储地址,所以字典是...

可可她爸爸
2017/12/19
0
0
Linux学习资料-more命令详解

more命令,功能类似 cat ,cat命令是整个文件的内容从上到下显示在屏幕上。 more会以一页一页的显示方便使用者逐页阅读,而最基本的指令就是按空白键(space)就往下一页显示,按 b 键就会往...

晓阳
2015/01/28
0
0
每天一个linux命令(12):more命令

more命令,功能类似 cat ,cat命令是整个文件的内容从上到下显示在屏幕上。 more会以一页一页的显示方便使用者逐页阅读,而最基本的指令就是按空白键(space)就往下一页显示,按 b 键就会往...

长平狐
2013/06/17
65
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring AOP之同一个对象方法内部自调用导致事务失效问题

对于像我这种喜欢滥用AOP的程序员,遇到坑也是习惯了,不仅仅是事务,其实只要脱离了Spring容器管理的所有对象,对于SpringAOP的注解都会失效,因为他们不是Spring容器的代理类,SpringAOP,就切入不...

xiaomin0322
33分钟前
1
0
Linux learn(七)

例行工作安排(定时任务)at,cron at 由atd服务提供,at指令所产生的的要运作的工作都以文本文件的方式写入 /var/spool/at/目录内,该工作便能等待at的这个服务取用与执行了。 权限限制相关...

lazy~
40分钟前
2
0
Vim与clang-format

前一段时间因工作需要参与了一个开源项目,在向github提交代码后提示格式校验失败。 项目的管理者告知,要想修改的代码能入库需要使用Clang-Format校验。 需要使用下面的命令对上次的修改重新...

DB_Terrill
42分钟前
1
0
Kafka写入数据保证不丢失

Kafka写入数据保证不丢失: 每个partition至少有一个follower在ISR列表中,跟上了Leader的数据同步 每次写入数据时,都要求至少写入partition leader成功,还至少一个ISR里的follower写入成功...

春哥大魔王的博客
49分钟前
1
0
git仓库删除所有提交历史记录,成为一个干净的新仓库

把旧项目提交到git上,但是会有一些历史记录,这些历史记录中可能会有项目密码等敏感信息。如何删除这些历史记录,形成一个全新的仓库,并且保持代码不变呢? 1.切换到新的分支 git check...

dragon_tech
52分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部