安徽网站建设网络公司,河北手机网站制作公司,建立一个虚拟公司的网站,手机百度2020最新版题目描述 从前#xff0c;小兔发现了一个神秘的花园。 花园是一个 n 行 m 列的矩阵#xff0c;第 i 行 j 列的花的美丽度为 ai,j#xff0c;一个合法的约会场所为任意一个正方形子矩阵#xff0c;定义子矩阵的浪漫度为这个子矩阵的两条对角线上的花的美丽度之和。 现在小兔… 题目描述 从前小兔发现了一个神秘的花园。 花园是一个 n 行 m 列的矩阵第 i 行 j 列的花的美丽度为 ai,j一个合法的约会场所为任意一个正方形子矩阵定义子矩阵的浪漫度为这个子矩阵的两条对角线上的花的美丽度之和。 现在小兔想选一个面积大等于 1 的约会场所使得场所的浪漫度最大以便和小鹿约会因为小兔忙着 AKIOI 所以她把这个问题交给了你。 输入 第一行两个正整数 n,m。 接下来是一个 n 行 m 列的矩阵表示各个位置上花的美丽度。 输出 仅一行一个正整数表示最大的浪漫度。 样例输入 Copy 3 3
2 -1 3
-4 2 1
1 2 -1样例输出 Copy 7提示 对于 40%的数据n,m≤10。 对于 100%的数据1≤n,m≤300,∣ai∣≤104。 #include cstdio
#include climits
int a[310][310];
long long sumz[310][310],sumf[310][310];
long long ans LLONG_MIN;
int main()
{int n, m;scanf(%d%d, n, m);for (int i 1; i n; i){for (int j 1; j m; j){scanf(%d, a[i][j]);sumz[i][j] sumz[i - 1][j - 1] a[i][j];sumf[i][j] sumf[i - 1][j 1] a[i][j];}}int b m n ? m : n, temp;for (int k 1; k b; k){for (int i 1; i n - k 1; i){for (int j 1; j m - k 1; j){temp sumz[i k - 1][j k - 1] - sumz[i - 1][j - 1] sumf[i k - 1][j] - sumf[i - 1][j k];if(k 1) temp - a[((i 1) k - 1) 1][((j 1) k - 1) 1];if (temp ans) ans temp;}}}printf(%lld\n, ans);return 0;
}
