C++14(g++5.4) 解法, 执行用时: 199ms, 内存消耗: 12136K, 提交时间: 2020-04-26 16:43:47

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int mod=998244353;
int pow(int,int,int);

const int N=1e3+5;

int n;

struct node{
    int y,x,w;
    bool operator<(const node&a)const{return w<a.w;}
}de[N*N];

int V[N],H[N];

inline int read(){
    int x=0,c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        x=x*10+c-'0';
    return x;
}

void init();
void work();
int ca=1;
int main(){
//    freopen("in.txt","r",stdin);
//    ios::sync_with_stdio(0);
//    cin.tie(0),cout.tie(0);
//    init();
//    int T;cin>>T;
//    while(T--)
    work();
    return 0;
}
void work(){
    n=read();
    int x,top=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            x=read();
            de[++top]=node{i,j,x};
        }
    }
    sort(de+1,de+top+1);
    int j=1;
    int ans=0;
    for(int i=1;i<=top;i++){
        if(de[i].w!=de[i-1].w){
            int mx=0;
            for(int k=j;k<i;k++){
                mx=max(mx,V[de[k].x]);
                mx=max(mx,H[de[k].y]);
            }
            mx++;
            ans=max(ans,mx);
            for(int k=j;k<i;k++){
                V[de[k].x]=max(V[de[k].x],mx);
                H[de[k].y]=max(H[de[k].y],mx);
            }
            j=i;
        }
    }
            int mx=0;
            for(int k=j;k<=top;k++){
                mx=max(mx,V[de[k].x]);
                mx=max(mx,H[de[k].y]);
            }
            mx++;
            ans=max(ans,mx);
    cout<<ans;
}
int pow(int a,int p,int m){
    int re=1;
    for(;p;p>>=1){
        if(p&1) re=1LL*re*a%m;
        a=1LL*a*a%m;
    }
    return re;
}

C++ 解法, 执行用时: 168ms, 内存消耗: 16080K, 提交时间: 2021-05-21 22:56:09

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 1e3 + 7;

int n;
struct E
{
    int n, x, y;
    bool operator < (const E& x) const
    {
        return n < x.n;
    }
}a[maxn * maxn];
int tot;
int b[maxn][maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> a[++tot].n;
            a[tot].x = i;
            a[tot].y = j;
        }

    sort(a + 1, a + 1 + tot);

    int bg = 1, _Max = 0;
    for (int i = 1; i <= tot; i++)
    {
        b[a[i].x][a[i].y] = max(b[a[i].x][0], b[0][a[i].y]) + 1;
        _Max = max(_Max, b[a[i].x][a[i].y]);

        if (i == tot || a[i].n != a[i + 1].n)
        {
            for (int j = bg; j <= i; j++)
            {
                b[a[j].x][a[j].y] = _Max;
                b[a[j].x][0] = max(b[a[j].x][0], b[a[j].x][a[j].y]);
                b[0][a[j].y] = max(b[0][a[j].y], b[a[j].x][a[j].y]);
            }
            b[0][0] = max(b[0][0], _Max);
            bg = i + 1;
            _Max = 0;
        }
    }

    cout << b[0][0] << "\n";

    return 0;
}