在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值
输入描述: 每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D : 3 <= N <= 100 1 <= D <= N 接下来有N行，每行N个数字d: 0 <= d <= 100
输出描述: 输出一个整数，表示找到的和的最大值
输入例子: 4 2 87 98 79 61 10 27 95 70 20 64 73 29 71 65 15 0
输出例子: 193
#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;int main(){ int n, d; cin >> n >> d; vector<vector<int>> vec(n, vector<int>(n, 0)); int w = 0; while (w<n) { int j = 0; while (j < n){ int x; cin >> x; vec[w][j] = x; ++j; } ++w; } vector<vector<int>> dp(n + 1 - d, vector<int>(n, 0)); for (int j = 0; j != n; ++j) { int k = 0; while (k <d){ dp[0][j] += vec[k][j]; ++k; } } for (int i = 1; i != n + 1 - d; ++i) { for (int j = 0; j != n; ++j) { dp[i][j] = dp[i - 1][j] + (vec[i + d - 1][j] - vec[i - 1][j]); } } int max1 = 0; int temp = 0; for (int i = 0; i != n + 1 - d; ++i){ for (int j = 0; j != n; ++j) { temp = dp[i][j]; if (temp>max1) max1 = temp; } } vector<vector<int>> dp1(n, vector<int>(n + 1 - d, 0)); for (int j = 0; j != n; ++j) { int k = 0; while (k <d){ dp1[j][0] += vec[j][k]; ++k; } } for (int i = 0; i != n; ++i) { for (int j = 1; j != n + 1 - d; ++j) { dp1[i][j] = dp1[i][j - 1] + (vec[i][j + d - 1] - vec[i][j-1]); } } int max2 = 0; temp = 0; for (int i = 0; i != n; ++i){ for (int j = 0; j != n + 1 - d; ++j) { temp = dp1[i][j]; if (temp>max2) max2 = temp; } } vector<vector<int>> dp2(n, vector<int>(n, 0)); for (int i = 0; i != n; ++i) { for (int j = 0; j != n; ++j) { int k = 0; int temp2 = 0; while (k < d&&i+k<n&&j+k<n){ temp2 += vec[i + k][j + k]; ++k; } dp2[i][j] = temp2; } } int max3 = 0; temp = 0; for (int i = 0; i != n; ++i){ for (int j = 0; j != n ; ++j) { temp = dp2[i][j]; if (temp>max3) max3 = temp; } } vector<vector<int>> dp3(n, vector<int>(n, 0)); for (int i = 0; i != n; ++i) { for (int j = 0; j != n; ++j) { int k = 0; int temp3 = 0; while (k < d&&i-k>=0&&j-k>=0){ temp3 += vec[i - k][j - k]; ++k; } dp3[i][j] = temp3; } } int max4 = 0; temp = 0; for (int i = 0; i != n; ++i){ for (int j = 0; j !=n; ++j) { temp = dp3[i][j]; if (temp>max4) max4 = temp; } } cout << max(max(max1, max2), max(max3, max4)) << endl; return 0;}新闻热点
疑难解答
