题目描述
操场，烈日，鸣蝉，偶尔一阵风吹过四周的香樟树，顿时感到一 阵凉爽。某大学大一新生正在进行军训。计算机系 1 班的 n 名（例如 6 人）同学，按照顺时针站成了一圈。教官要求从第 1 个人开始报数， 数到第 m 个（例如第 2 个）就出列，出列的人站成一排，如此这般， 直至 n 个人全部出列（出列顺序 2 号，4 号，6 号，3 号，1 号，5 号）。 以出列后的队伍为准，在不改变同学们站立顺序的前提下，从队伍中 选出若干个人，使得他们的身高呈上身趋势，请统计最多可以选出的人数。
输入格式
两行。第一行两个正整数 n 和 m；第二行 n 个人的身高（都是整数， 单位 cm）。
输出格式
一行。一个整数，表示可以选出的最多的人数。
输入输出样列
输入样例1：
6 2
176 175 192 168 180 170
输出样例1：
4
说明
出列顺序 246315，选择 4615，一共 4 人，人数最多。
数据范围： 1<=n<=50,1<=m<=9,150<=身高都是整数<=200。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>
using namespace std;
int a[110],f[110],b[110],dp[110];
int main()
{
int n,m,pos=1;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
int t=m;
while(t){
if(pos==n+1){
pos=1;
}
if(f[pos]==0){
pos++;
t--;
}else{
pos++;
}
}
b[i]=a[pos-1];
f[pos-1]=1;
}
int maxn=-1;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(b[i]>b[j]){
dp[i]=max(dp[j]+1,dp[i]);
}
}
maxn=max(dp[i],maxn);
}cout<<maxn;
return 0;
}
|
