CCPC2019年河南省赛——最大下降矩阵（简单DP）

灰太狼 2022-02-19 10:15 186阅读 0赞

#                                        最大下降矩阵 #

### 题目链接： ###

[http://acm.zzuli.edu.cn/problem.php?id=2518][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 ###

### 提示 ###

样例二

### 输入 ###

3 1  
3  
1  
2

### 输出 ###

### 题目描述： ###

给出一个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;
    }

[http_acm.zzuli.edu.cn_problem.php_id_2518]: http://acm.zzuli.edu.cn/problem.php?id=2518