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://www.uj5u.com/qita/280352.html
標籤：其他
上一篇：全景圖