[蓝桥杯2022初赛] 统计子矩阵

[蓝桥杯2022初赛] 统计子矩阵

内存限制：256 MB
时间限制：1 S

题目描述

给定一个 N × M 的矩阵A，请你统计有多少个子矩阵(最小 1 × 1，最大 N × M) 满足：
子矩阵中所有数的和不超过给定的整数K?

输入格式

第一行包含三个整数N, M 和K.
之后 N 行每行包含 M 个整数，代表矩阵A.
30%的测试数据：1≤N,M≤20；
70%的测试数据：1≤N,M≤100；
100%的测试数据：1≤N,M≤500；0≤Aij≤1000；1≤K≤250000000。

输出格式

一个整数代表答案。

输入样例

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

输出样例

19

数据范围与提示

满足条件的子矩阵一共有19，包含：
大小为1 × 1 的有10 个。
大小为1 × 2 的有3 个。
大小为1 × 3 的有2 个。
大小为1 × 4 的有1 个。
大小为2 × 1 的有3 个。

分类标签

进阶题 枚举

代码(一维）

#include "stdio.h"
#define ll long long
ll dp[509][509];
int main()
{int n,m,k;ll sum=0;scanf("%d %d %d",&n,&m,&k);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%lld",&dp[i][j]);dp[i][j]+=dp[i-1][j];//纵坐标前缀和 }}//双指针666 for(int i=1;i<=n;i++)//矩阵的起始横坐标 {for(int ii=i;ii<=n;ii++)//矩阵的终点纵坐标 {ll s=0;for(int j=1,jj=1;jj<=m;jj++)// j矩阵起始纵坐标，jj矩阵终点纵坐标 {s=s+dp[ii][jj]-dp[i-1][jj];while(s>k){s=s-(dp[ii][j]-dp[i-1][j]);//改变矩阵起始纵坐标 j++;}sum+=jj-j+1;}}}printf("%lld\\n",sum);
}