问题2518--最大下降矩阵

2518: 最大下降矩阵

时间限制: 1 Sec  内存限制: 512 MB
提交: 1564  解决: 456
[状态] [讨论版] [提交] [命题人:]
题目描述
我们称一个矩阵是下降矩阵,当且仅当,矩阵的每一列都是严格下降的。很显然,这个要求很苛刻,大多数矩阵都无法满足。但是显然如果消去一些行,一定可以使得这个矩阵变成下降矩阵。

现在给出一个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


来源/分类