「JoyOI1466」最美妙的矩阵
背景 Background
Candy的生日即将到来，飘飘乎居士希望找到一个最美妙的矩阵送个Candy作为礼物
描述 Description
飘飘乎居士从Pink处得知最美妙的矩阵满足三个条件：首先，它的长和宽都必须和矩阵的边界平行（也就是不可以出现斜的矩阵）；第二：子矩阵横竖都要满足单调递增（可以相等，也就是对于每一个最优子矩阵的元素都要满足a[i][j]>=a[i-1][j] and a[i][j]>=a[i][j-1]，其中a[i][j]表示矩阵第i行第j列的数字）；第三：最优矩阵是在满足上述两个条件中面积最大的矩阵。
输入格式 InputFormat
第一行，两个正整数n，m
接下来n行，每行m个数字，构成一个n*m的矩阵
输出格式 OutputFormat
一行，代表最优矩阵的面积
数据范围和注释 Hint
最优子矩阵为
2 4 4
4 4 4
该矩阵满足横竖都单调递增，并且是所有满足条件中面积最大的。其中矩阵长为3宽为2，面积为6，也就是最后的答案。
对于30%的数据 0<n m<=50
对于100%的数据 0<n m<=200
对于所有数据 a[i][j]<=20000000
| 时间及空间复杂度 | 题解 |
| 时间复杂度：O(n^6)
空间复杂度：O(n^2) |
方法一：枚举子矩阵的每一个左上角坐标和右下角坐标，在逐个检查枚举的矩阵是否符合单调特性。预期得分30 |
| 时间复杂度：O(N^3)
空间复杂度：O(N^3) |
方法二：预处理column[i][j]以及can[i][j][k]数组。
其中column[i][j]表示坐标为i j的点能向上单调递减的长度。则 column[i][j]={column[i-1][j]+1(a[i][j]>=a[i-1][j]),column[i][j]=1}
用can[i][j][k]表示从第i行到第j行中的第k列能否接道第i行到第j行的k-1列中，则关于can[i][j][k]=true的条件为 (can[i][j-1][k])and(column[j][k]>=j-i+1)and(a[j][k]>=a[j][k-1])and(coulumn[j][k-1]>=j-i+1。
接下来用f[i][j][k]表示从第i行到第j行中，第k列的最大子矩阵 F[i][j][k]=f[i][j][k-1]+j-i+1 (can[i][j][k]=true) =j-i+1 (can[i][j][k]=false and column[j][k]>=j-i+1) =0 （else） 预期得分100 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<iostream> #include<cstdio> using namespace std; int n,m,a[201][201],u[201][201],f[201][201][201],ans; bool can[201][201][201]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]>=a[i-1][j])u[i][j]=u[i-1][j]+1; else u[i][j]=1; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) for(int k=1;k<=m;k++){ if((can[i][j-1][k]||j-1<i)&&u[j][k]>=j-i+1&&a[j][k]>=a[j][k-1]&&u[j][k]>=j-i+1) can[i][j][k]=1;} for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) for(int k=1;k<=m;k++) { if(can[i][j][k])f[i][j][k]=f[i][j][k-1]+j-i+1; else if(u[j][k]>=j-i+1)f[i][j][k]=j-i+1; ans=max(ans,f[i][j][k]); } printf("%d",ans); return 0; } |
OI 课件=>
