$$打磚塊$$

Description

KXT是一個很無聊的小朋友，一天到晚都在打坐…

一天，被他發現了一個比打坐更無聊的事情——打磚塊。很多塊磚分布在一個m×m的矩陣中，他可以消掉以他為左上角頂點的一個n×n的矩陣里的所有磚塊。

喜歡偷懶的他請來了你幫他計算可以消掉最多的磚塊數（只能消一次）。

Input

第一行：用空格隔開的三個整數n、m、k。

接下來k行，每行2個用空格隔開的整數Xi、Yi，表示第i塊磚在Xi行、Yi列的位置。

Output

為可以消掉最多的磚塊數。

Sample Input

5 10 11

2 1

4 6

4 9

3 9

9 7

9 9

7 9

8 10

8 8

8 6

10 2

Sample Output

6

Hint

【樣例解釋】 　 [外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-m0D5u8xZ-1625489129772)(http://10.156.17.250/JudgeOnline/image/2215.jpg)]

站在第4行、6列的位置，可以消除6個方塊。

【數據范圍】

n<=m; k<=m*m

60%：n<=70; m<=70; k<=4900

100%：n<=1000; m<=1000; k<=1000000;

解題思路

枚舉正方形中左上角的點，因為不存在負數，右下角的點就是s[i+n-1][j+n-1]，在按照狀態轉移方程做出此題

$$s[i][j]=s[i?1][j]+s[i][j?1]?s[i?1][j?1]+s[i][j]$$
$$ans=max(ans,s[i+n?1][j+n?1]?s[i+n?1][j?1]?s[i?1][j+n?1]+s[i?1][j?1])$$

#include<cstdio> #include<iostream> using namespace std; int n,m,k,ans,x,y,s[1003][1003]; int main() {scanf("%d%d%d",&n,&m,&k);for (int i=1;i<=k;i++){scanf("%d%d",&x,&y);s[x][y]++;}for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];//求出前綴和for (int i=1;i<=m-n+1;i++)for (int j=1;j<=m-n+1;j++)ans=max(ans,s[i+n-1][j+n-1]-s[i+n-1][j-1]-s[i-1][j+n-1]+s[i-1][j-1]);//計算當前面積printf("%d",ans); }

總結

以上是生活随笔為你收集整理的【动态规划】打砖块的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。