2518: 最大下降矩阵

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 typedef long long ll;
 5 ll a[305][305];
 6 ll n,m,sum;
 7 ll goback[305],maxlen[305];
 8 bool ican(ll i,ll j){
 9     for(int u=1;u<=m;u++) if(a[j][u]<=a[i][u]) return false;
10     return true;
11 }
12 int main(){
13     scanf("%ld%ld",&n,&m);
14     for(int i=1;i<=n;i++)
15         for(int j=1;j<=m;j++)
16             scanf("%ld",&a[i][j]);
17     maxlen[1]=1;sum=1;
18     for(int i=1;i<=n;i++){
19         ll k=0;
20         for(int j=1;j<n;j++){
21             if(ican(i,j)){
22                 k=max(k,maxlen[j]);
23                 if(k==maxlen[j]) goback[i]=j;
24             }
25             maxlen[i]=k+1;
26             sum=max(sum,maxlen[i]);
27         }
28     }
29     //for(int i=1;i<=n;i++) printf("%ld ",maxlen[i]);
30     printf("%ld",n-sum);
31     return 0;
32 }