南京理工大学第八届程序设计大赛(校外镜像) F sequence 一时失言乱红尘 2022-08-21 06:50 115阅读 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; }
还没有评论，来说两句吧...