最大下降矩阵

题目链接：

http://acm.zzuli.edu.cn/problem.php?id=2518

题目描述

我们称一个矩阵是下降矩阵，当且仅当，矩阵的每一列都是严格下降的。很显然，这个要求很苛刻，大多数矩阵都无法满足。但是显然如果消去一些行，一定可以使得这个矩阵变成下降矩阵。

现在给出一个n行m列的矩阵，请你求出最少消去多少行，可以使得这个矩阵变为下降矩阵。

输入

输入第一行包含两个正整数n,m分别表示矩阵的行数和列数。(1<=n,m<=300)
接下来n行，每行有m个数,中间用空格隔开，每个数都小于2^31.

输出

输出仅包含一个整数，即最少消去的行数。

样例输入 Copy

1 3
1 2 3

样例输出 Copy

0

提示

样例二

输入

3 1
3
1
2

输出

1

题目描述：

给出一个n*m矩阵问使得此矩阵为最大下降矩阵最少要削去多少行。

解题思路：

与求最大上升子序列类似，求出最大下降矩阵，总行数减去最大下降矩阵行数，为最少削去行数。

程序代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
	int n,m,j,i,k,tmp,len[330],f,maxx;
	long long a[330][330];
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(len,0,sizeof(len));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%lld",&a[i][j]);
		len[1]=1;
		for(i=2;i<=n;i++)
		{
			tmp=0;
			for(j=1;j<i;j++)
			{
				f=0;
				for(k=1;k<=m;k++)
				{
					if(a[i][k]>=a[j][k])
					{
						f=1;
						break;
					}
				}
				if(f==0)
				{
					if(tmp<len[j])
						tmp=len[j];
				}
			}
			len[i]=tmp+1;
		}
		maxx=1;
		for(i=1;i<=n;i++)
		{
			if(maxx<len[i])
			{
				maxx=len[i];
			}
		}
		printf("%d\n",n-maxx);
	}
	return 0;
}