The maximum descent matrix of Henan saiccpc

Title Description

We call a matrix a descent matrix, if and only if every column of the matrix is strictly descent. Obviously, this requirement is very demanding, and most matrices can not meet it. But obviously if we delete some lines, we can make this matrix become a descent matrix.

Now we give a matrix of n rows and m columns. Please find out the minimum number of rows to be eliminated, which can make this matrix become a descending matrix.

input

The first input row contains two positive integers n,m representing the number of rows and columns of the matrix. (1 < = n,m < = 300)
Next n lines, each line has m numbers, separated by spaces, each number is less than 2 ^ 31

output

The output contains only one integer, the minimum number of rows to be eliminated.

Sample inputCopy

1 3
1 2 3 

sample output Copy

0

Tips

Example two
Input
3 1 



Output


 

Source / classification

Train of thought:

Naked lis longest ascending subsequence

#include<iostream>
#include<cstring>
#define inf 0x3f3f3f3f3f3f
using namespace std;
long long a[1009][1009],dp[3002];
int main()
{
    long long n,m;
    while(~scanf("%lld%lld",&n,&m))
    {
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        for(long long i = 1; i <= n;++i)
        {
            for(long long j = 1;j <= m;++j)
            {
                scanf("%lld",&a[i][j]);
            }
        }
        long long max1 = -inf;
        for(long long i = 1; i <= n;++i)
        {
            dp[i] = 1;
            for(long long j = 1;j < i;++j)
            {
                bool flag = false;
                for(long long k = 1; k <= m;++k)//Enumerate whether each row has a descending relationship with the previous row
                {
                    if(a[j][k]>a[i][k])
                    {
                         
                    }
                    else{
                        flag = true;break;//Not established
                    }
                }
                if(!flag)
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            max1 = max(dp[i],max1); 
        }   
        printf("%lld\n",n-max1);    
    }
             
    return 0;
}

 

Tags: less

Posted on Thu, 28 Nov 2019 09:22:18 -0800 by chris_rulez001