【tyvj1466】最美妙的矩阵

现在的位置: 首页 > 综合 > 正文

【tyvj1466】最美妙的矩阵

2017年04月26日 ⁄ 综合 ⁄ 共 1873字 ⁄ 字号小中大 ⁄ 评论关闭

背景 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

一行，代表最优矩阵的面积

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

C++

1

6

数据范围和注释 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

#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;
}

继续

http://blog.csdn.net/willinglive/article/details/39723903

【上篇】GCD题目汇总
【下篇】【poj3150】Cellular Automaton

作者: fireproof

该日志由 fireproof 于7年前发表在综合分类下，最后更新于 2017年04月26日.
转载请注明: 【tyvj1466】最美妙的矩阵 | 学步园 +复制链接

抱歉!评论已关闭.

学步园