P2092 tj002

by 2021tyoi0103——2022-04-09 21:25:54

返回

# 折型最大 ## 题目描述 折型在日常生活中随处可见，比如闪电符号“ ” ，显示器的四个角等等；折型大致可以 分为四种类型（“┌”，“┐”，“└”，“┘”）。笨笨只对“┘”这种折型特别感兴趣（萝卜青菜， 各有所爱），笨笨想在一个二维矩阵中求“┘”这种数字加和最大的折型，具体规定如下描述： 对于一个 N 行*M 列的矩阵，一个折型区域必须满足： 1、它的形状为“┘”（不能是“└”，“┌”，或“┐”）； 2、它的宽度为 1； 3、它的横向长度和纵向长度都必须大于 1 且连续，不能等于 1（即不能退化为一条线或一 个点）； 现给出这个二维矩阵，求其中数字和最大的这种折型区域。 ## 输入 第一行为 N,M，中间用一个空格隔开， N 表示矩阵的行数， M 表示矩阵的列数； 接下来是 N 行，每行 M 个整数，每 2 个整数之间用 1 个空格隔开，每个整数 A[i,j]在[-100,100]； ## 输出 一行一个整数，即满足题目要求的折型区域的最大数字和。 ## 提示  【样例解释】 如右图所示，符合要求的折型区域数字和最大 【数据规模】 对于 30%的数据： 2≤M,N≤100； 对于 60%的数据： 2≤M,N≤500； 对于 100%的数据： 2≤M,N≤1,000； -100≤A[i,j]≤100；## 样例 ### #1 输入数据 ``` 4 4 -2 5 0 3 -1 1 0 -3 3 -2 -4 -6 -3 5 -5 5 ``` 输出数据 ``` 7 ``` ## 分析 这题基本上可以分成两个做法，一个是60分的做法，一个是100分的做法 ### 60分做法 可以遍历上面中间和左边的三个点求出最值，但显然时间复杂度跟高，到了```O(n^3)```只能得60分。 ### 满分做法 先定义两个数组f1和f2都是二维的，然后第一个数组表示[i][j]这个位置向上连和最大的方案的和， 第二个数组表示[i][j]这个位置向左连和最大的方案的和， 最后再将两个数组合起来，这道题就做完了。 ### 需要注意的几个点： 1.f1 和 f2两个数组每一个数必须至少是两个数的和(要不可能输出的方案是一个横着的线或者竖着的线) 2.最后遍历时第一行和第一列不能遍历（要不也可能变成一条线） ### 上ac代码 ``` #include<iostream> using namespace std; int f1[1010][1010],f2[1010][1010],a[1010][1010],n,m; int main(){ cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin >> a[i][j]; f1[i][j] = -1000000; f2[i][j] = -1000000; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ f1[i][j] = max(f1[i][j-1]+a[i][j],a[i][j]+a[i][j-1]); f2[i][j] = max(f2[i-1][j]+a[i][j],a[i][j]+a[i-1][j]); // cout << f2[i][j] << " "; } // cout << endl; } int maxn = -1000000; // cout << maxn << endl; for(int i=2;i<=n;i++)for(int j=2;j<=m;j++){ // maxn = max(maxn,f1[i][j]+f2[i][j]); if(f1[i][j]+f2[i][j]-a[i][j]>maxn){ maxn = f1[i][j]+f2[i][j]-a[i][j]; // cout << maxn <<" "<<i <<" "<<j<<" "<< f1[i][j]<<" "<<f2[i][j]<< endl; } } cout << maxn << endl; }/************************************************************** Language: C++ Result: 正确100 Time:212 ms Memory:13668 kb ****************************************************************/ ```

赞(2)

+1