自己做的网站本地调试,百度sem竞价推广,邢台中北世纪城网站兼职,新桥专业网站建设题干#xff1a;
给定一个NxM的矩阵A和一个整数K#xff0c;小Hi希望你能求出其中最大#xff08;元素数目最多#xff09;的子矩阵#xff0c;并且该子矩阵中所有元素的和不超过K。
Input
第一行包含三个整数N、M和K。
以下N行每行包含M个整数#xff0c;表示A。
对…题干
给定一个NxM的矩阵A和一个整数K小Hi希望你能求出其中最大元素数目最多的子矩阵并且该子矩阵中所有元素的和不超过K。
Input
第一行包含三个整数N、M和K。
以下N行每行包含M个整数表示A。
对于40%的数据1 N, M 10
对于100%的数据1 N, M 250 1 K 2147483647 1 Aij 10000
Output
满足条件最大的子矩阵所包含的元素数目。如果没有子矩阵满足条件输出-1。
Sample Input
3 3 9
1 2 3
2 3 4
3 4 5
Sample Output
4 解题报告
先预处理一个前缀和然后枚举每两行然后行内尺取就行了总复杂度N^3,。可以尺取的前提是元素都是正数。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
int n,m,k;
ll a[255][255],sum[255][255];
int main()
{cinnmk;for(int i 1; in; i) {for(int j 1; jm; j) {scanf(%lld,a[i][j]);}}for(int i 1; in; i) {for(int j 1; jm; j) {sum[i][j] a[i][j] sum[i-1][j] sum[i][j-1] - sum[i-1][j-1]; }}int ans -1;for(int i 1; in; i) {for(int j i; jn; j) {int l 1,r 1;ll tmp 0;while(r m) {tmp sum[j][r] - sum[j][r-1] - sum[i-1][r] sum[i-1][r-1];while(lr tmp k) {tmp - sum[j][l] - sum[j][l-1] - sum[i-1][l] sum[i-1][l-1];l;}if(tmp k)ans max(ans,(j-i1)*(r-l1)); r;}}}if(ans 0) printf(-1\n);else printf(%d\n,ans);return 0 ;
}
