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

                                       最大下降矩阵

题目链接:

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;
}
全部评论

相关推荐

坐标北京,今天和同事一起吃晚饭的时候,听研发说今天面试的1个实习生,疑似使用AI回答问题,说那个男生全程眼神飘忽,不看镜头,眼神向下看应该是在看屏幕,提问项目的时候,话术很AI套话,简单来说就是没有中译中,mentor他们聊天说,以后在招聘优先找能来公司面试的,反正在北京也不缺实习生😂😂
从零开始的转码生活:为啥还要线下,如果mt判断不出来面试的人是否使用ai回答只能说明两件事,一件是本人水平不行,ai话术都判断不出来,还有就是问题问的不行,不能根据项目和经历临时提问,你问的深一点哪有ai的事,而且遇到用ai回答问题的就给挂了呗,又不是所有线上的都用ai,而且我线上面试也不会看镜头,我在回忆的时候眼睛是不会盯着屏幕的
点赞 评论 收藏
分享
迟缓的斜杠青年巴比Q了:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务