首页 > 电脑常识 > 电脑常识

New Year and Domino

admin 电脑常识 2021-04-26 15:56:46  
后台-系统设置-扩展变量-手机广告位-内容正文底部

https://codeforces.com/problemset/problem/611/C

题意:给一个n行m列的由.和*组成的二维数组,横着的两个或者竖着的两个点点都符合条件,再给q对点(左上角和右下角)之间的矩形,然后问询问区间内符合条件的两连点有多少个。
在这里插入图片描述

一开始的想法就是枚举每一个点的竖着的两个和横着的两个是否符合,增加总和,但是写出来发现是一个三重循环,好吧,肯定超时
那他一定又是一个我不擅长的DP题了。搜搜搜,查查查,搞懂了,果然属于DP中的二维前缀和类。
有一点像“矩形的面积”那样,把一整块区域的值都加起来。

这里附上一张盗取的图,帮助了解二维前缀和,也可以自行去学习。图片出处
在这里插入图片描述

所以这个题最大的矩形前缀和就等于蓝的矩阵加上黄的矩阵,也就是横着加竖着再减去重叠面积,求出所有符合要求的情况。
前缀和的状态转移方程:
sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1]
然后我们最后需要的是

#include <iostream>
#include <cstdio>
 
using namespace std;
 
char m[505][505];
int a[505][505];
int b[505][505];
 
int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>m[i][j];
        }
    }
    for(int i=1;i<=h;i++)//利用公式预先求出所有情况
    {
        for(int j=1;j<=w;j++)
        {
            if(m[i][j]=='.' && m[i-1][j]=='.') a[i][j]++;
            if(m[i][j]=='.' && m[i][j-1]=='.') b[i][j]++;
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//横着,并未加红色部分
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];//竖着
        }
    }
    int x1,y1,x2,y2,q;
    cin>>q;
    while(q--)//这样的直接用,就省了一重循环
    {
       int sum=0;
        cin>>x1>>y1>>x2>>y2;
        //加上红色部分
        sum+=a[x2][y2]-a[x1][y2]-a[x2][y1-1]+a[x1][y1-1];//横着
        sum+=b[x2][y2]-b[x1-1][y2]-b[x2][y1]+b[x1-1][y1];//竖着
        cout<< sum <<endl;
    }
    return 0;
}

文章来源:https://blog.csdn.net/qq_51392086/article/details/115977676

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://jcdi.cn/diannaochangshi/diannaochangshi/673.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码