南京理工大学第八届程序设计大赛(校外镜像) F sequence

一时失言乱红尘 2022-08-21 06:50 165阅读 0赞

# sequence #

Time Limit: 1000MS

Memory Limit: 65536KB

## Description ##

将一个给定的数列，拆分成K个不降序列，每个数出现且只出现一次，且在各序列中各个数相对于原数列的相对顺序不变。如7 6 9 8 10可以拆成 7 9 10和6 8。求最小的K值。

## Input ##

第一行输入一个整数T（1 <= T <= 100），表示接下来T组测试数据，每组两行，第一行为n，代表数列长度（1<=n<=10000）接下来一行有n个数，空格分隔（每个数<=50000）。

## Output ##

对每组数据输出一个最小的K值。

## Sample Input ##

2
    5
    7 6 9 8 10
    5
    5 4 3 2 1

## Sample Output ##

2
     5 #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int x[10005];
    int slove(int n)
    {
    	int vis[10005]={0},kase=0,ans=0;
    	for(int i=0;i<n;++i)
    	{
    		if(!vis[i])
    		{
    			kase=i;
    			for(int j=i+1;j<n;++j)
    			{
    				if(!vis[j]&&x[kase]<=x[j])
    				{
    					vis[j]=1; 
    					kase=j;
    				}
    			}
    			++ans;
    		}
    	}
    	return ans;
    }
    int main()
    {
    	int t;
    	//freopen("shuju.txt","r",stdin);
    	scanf("%d",&t);
    	while(t--)
    	{
    		int n;
    		scanf("%d",&n);
    		for(int i=0;i<n;++i)
    		{
    			scanf("%d",&x[i]);
    		}
    		printf("%d\n",slove(n));
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，165人围观）

还没有评论，来说两句吧...

相关阅读

相关南京理工大学第八届程序设计大赛(校外镜像) J sequence

water1 Time Limit: 1000MS Memory Limit: 65536KB Description 听说全球气候变暖，冰川融化，海水淹大地。

我不是女神ヾ/ 2022年08月21日 06:50/ 0 赞/ 153 阅读

相关南京理工大学第八届程序设计大赛(校外镜像) F sequence

sequence Time Limit: 1000MS Memory Limit: 65536KB Description 将一个给定的数列，拆分成K个不降序列

一时失言乱红尘/ 2022年08月21日 06:50/ 0 赞/ 166 阅读

相关开锁魔法II 哈尔滨理工大学第五届ACM程序设计竞赛

规律： a\[i\]\[j\]= 1/i \ a\[i-1\]\[j-1\] + (i-1)/i \ a\[i-1\]\[j\]; (少一个盒子时使用j-1

朱雀/ 2022年08月07日 09:55/ 0 赞/ 211 阅读

相关南京理工大学第八届程序设计大赛(校外镜像) A 偷吃糖果

偷吃糖果 Time Limit: 1000Ms Memory Limit: 65536KB Description 小鱼喜欢吃糖果。他有两盒糖果，两盒糖果分别仅

叁歲伎倆/ 2022年07月29日 11:57/ 0 赞/ 132 阅读

相关第六届河南省程序设计大赛——F Card Trick

题目描述: The magician shuffles a small pack of cards, holds it face down and performs th

清疚/ 2022年04月24日 22:34/ 0 赞/ 197 阅读

相关第九届河南理工大学算法程序设计大赛 H. Mo的面积

题目链接：[https://www.hpuoj.com/contest/16/problem/H/][https_www.hpuoj.com_contest_16_proble

快来打我*/ 2022年02月24日 10:14/ 0 赞/ 182 阅读

相关第九届河南理工大学算法程序设计大赛 C. Asia区域宫

题目链接：[https://www.hpuoj.com/contest/16/problem/C/][https_www.hpuoj.com_contest_16_proble

约定不等于承诺〃/ 2022年02月24日 02:36/ 0 赞/ 210 阅读

相关第五届河南省程序设计大赛——F Metric Matrice

题目描述: Given as input a square distance matrix, where a\[i\]\[j\] is the distance betw

柔光的暖阳◎/ 2022年02月12日 15:37/ 0 赞/ 242 阅读

相关长春理工大学第十四届程序设计竞赛（重现赛）B

B Bowling Game 题目链接：[https://ac.nowcoder.com/acm/contest/912/B][https_ac.nowcoder.com

我会带着你远行/ 2022年01月07日 15:35/ 0 赞/ 260 阅读

相关长春理工大学第十四届程序设计竞赛（重现赛）J

J.Printout 题目：链接：[https://ac.nowcoder.com/acm/contest/912/J][https_ac.nowcoder.com_a

淩亂°似流年/ 2022年01月07日 15:35/ 0 赞/ 262 阅读