PAT甲级1045-程序员宅基地

技术标签: 算法  PAT  hash  

PAT甲级1045

题目大意:给出总颜色数n(好像没什么用),eva喜欢的颜色数m,还有可供挑选的颜色数l,求出从l个颜色当中取出eva喜欢的颜色序列最大长度是多少(必须按她喜欢的顺序排列)
LIS问题,这里尽量不要写find函数查找是不是eva喜欢的颜色,后面两个测试点会超时,用hash数组存放,如果不是eva喜欢的颜色就置为-1,若是则存放该颜色所在位置。然后开辟一个数组踢掉待选颜色中所有eva不喜欢的颜色即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,m,l;
int favoriteColor[210];
int stripeColor[10010];
vector<int> a;
int favColor[210];	//记录是否是eva喜欢的颜色并且记录位置
int main(){
    
	scanf("%d%d",&n,&m);
	int length=0;
	fill(favColor,favColor+210,-1);
	for(int i=0;i<m;i++){
    
		scanf("%d",&favoriteColor[i]);
		favColor[favoriteColor[i]]=i;
	}
	scanf("%d",&l);
	int dp[l];
	for(int i=0;i<l;i++){
    
		scanf("%d",&stripeColor[i]);
		if(favColor[stripeColor[i]]!=-1) a.push_back(stripeColor[i]);
	}
	for(int i=0;i<a.size();i++){
    
		dp[i]=1;
		for(int j=0;j<i;j++){
    
			if(favColor[a[j]]<=favColor[a[i]]&&dp[j]+1>dp[i])
				dp[i]=dp[j]+1;
		}
		length=max(dp[i],length);
	}
	printf("%d",length);
	system("pause");
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zerohawk/article/details/114656230

智能推荐

如何做一个“实用”的图像数据集_影像数据集结合图制作-程序员宅基地

文章浏览阅读1.4k次。目录 引言 一、探究数据的“用途” 二、梳理专业的“知识” 三、数据与知识“迭代” 四、确定性能的“指标” 五、总结 鸣谢、文献 编者序 大家都说这是一个大数据的年代,人工智能的落地需要数据, 深度学习更需要海量数据。于是, 出现了一个流行的口号:“数据就是新的石油“(D..._影像数据集结合图制作

对用户信息显示进行处理,保证用户信息安全,如银行卡卡号,姓名,手机号等_代码君小飞-程序员宅基地

文章浏览阅读2k次。场景:项目中有个地方,用户输入订单号,然后显示对应的用户信息,银行要求我们将对应的用户信息进行处理,以保证用户的信息安全import java.util.regex.Pattern;/*** @author 作者:代码君小飞* @version 创建时间:2018年5月22日 上午10:50:08**/public class Test {public static ..._代码君小飞

vue 集成 cesium_vue集成cesium-程序员宅基地

文章浏览阅读1.9k次。Vue-cli4 集成 Cesium加载显示 Geojson_vue集成cesium

office2016 excel复制粘贴就卡死_excel2016复制就卡死-程序员宅基地

文章浏览阅读9.5k次。office2016 excel复制粘贴就卡死_excel2016复制就卡死

CTF-Web-[极客大挑战 2019]PHP_2019 ctf php-程序员宅基地

文章浏览阅读2k次,点赞7次,收藏4次。CTF-Web-[极客大挑战 2019]PHP博客说明文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!本文仅用于学习与交流,不得用于非法用途!CTP平台网址https://buuoj.cn/challenges题目Web类,[极客大挑战 2019]PHP打开题目的实例思路看到这种题目,我爱了特别是这个动画效果..._2019 ctf php

像素深度(bpp)_2bpp-程序员宅基地

文章浏览阅读7.7k次,点赞5次,收藏18次。像素深度是指存储每个像素所用的位数,它也是用来度量图像的分辨率。像素深度决定彩色图像的每个像素可能有的颜色数,或者确定灰度图像的每个像素可能有的灰度级数。例如,一幅彩色图像的每个像素用R,G,B三个分量表示,若每个分量用8位,那么一个像素共用24位表示,就说像素的深度为24,每个像素可以是16 777 216(2的24次方)种颜色中的一种。在这个意义上,往往把像素深度说成是图像深度。表示一个像_2bpp

随便推点

poj 2253 Frogger(dijkstra变形,好题)_frogger dijkstra 题目有问题-程序员宅基地

文章浏览阅读313次。题目链接FroggerTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 37972 Accepted: 12216DescriptionFreddy Frog is sitting on a stone in the middle of a_frogger dijkstra 题目有问题

我面了昆仑天工大模型算法岗,题是真硬啊。。。-程序员宅基地

文章浏览阅读1k次,点赞35次,收藏28次。Transformer 的结构主要包括:Encoder:由多层自注意力机制模块和全连接前馈神经网络组成,用于将输入序列编码成隐藏表示。Decoder:由多层自注意力机制模块、编码器-解码器注意力机制模块和全连接前馈神经网络组成,用于生成目标序列。

golang微服务框架go-micro 入门笔记1.搭建 go-micro环境-程序员宅基地

文章浏览阅读178次。微服务的本质是让专业的人做专业的事情,做出更好的东西。golang具备高并发,静态编译等特性,在性能、安全等方面具备非常大的优势。go-micro是基于golang的微服务编程框架,go-micro操作简单、编码高效、功能强大。但是网络上资料偏少,本系列文章定位最简单最容易上手的go-m...

【蓝桥杯省赛真题31】Scratch热气球 少儿编程scratch蓝桥杯省赛真题讲解_csdn scratch 热气球-程序员宅基地

文章浏览阅读1.1k次。scratch上升的热气球第十三届蓝桥杯scratch省赛真题一、题目要求编程实现1.点击绿旗,角色,背景如图所示2.等待1秒,热气球向舞台上方移动(能看到移动过程)3.热气球碰到舞台上方停止移动,等待1秒后,热气球从舞台上方飞出二、案例分析1、角色分析角色:热气球2、背景分析背景:Beach3、前期准备1.删除默认的小猫角色,添加热气球到角色列表中,如下图所示:2.添加Beach到背景中,并删除默认的空白背景,如下图所示:三、解题思路.._csdn scratch 热气球

VS2017调试C程序加载非常慢,弹出加载框:“正在从以下位置加载........尝试取消禁用后续符号加载”_尝试取消将禁用后续符号加载-程序员宅基地

文章浏览阅读1w次,点赞22次,收藏33次。今天在调试C程序时出现一个问题,VS弹出一个提示框,显示正在从以下位置加载ntdll.dll的符号:Microsoft符号服务器,尝试取消将禁用后续符号加载。从提示的信息来看,程序应该是在进行符号加载时出现了问题,导致了需要从其他位置加载符号服务器。当加载完ntdll.dll后,陆续又加载了几个dll的符号,以下是加载时的截图: ..._尝试取消将禁用后续符号加载

STM32F103使用内部Flash保存参数_st32f103 基于hal库用flash保存参数-程序员宅基地

文章浏览阅读2.4w次,点赞21次,收藏104次。在我们应用开发时,经常会有一些程序运行参数需要保存,如一些修正系数。这些数据的特点是:数量少而且不需要经常修改,但又不能定义为常量,因为每台设备可能不一样而且在以后还有修改的可能。将这类数据存在指定的位置,需要修改时直接修改存储位置的数值,需要使用时则直接读取,会是一种方便的做法。考虑到这些数据量比较少,使用专门的存储单元既不经济,也没有必要,而STM32F103内部的Flash容量较大,..._st32f103 基于hal库用flash保存参数