广州建设工程交易中心网站,北京网站建设那些,wordpress 获取当前文章栏目链接,网络推广方式和方法【题目描述】
n 位同学站成一排#xff0c;音乐老师要请其中的 n−k 位同学出列#xff0c;使得剩下的 k 位同学排成合唱队形。
合唱队形是指这样的一种队形#xff1a;设 kk 位同学从左到右依次编号为 1,2, … ,k#xff0c;他们的身高分别为,, … ,#xff0c;则…【题目描述】
n 位同学站成一排音乐老师要请其中的 n−k 位同学出列使得剩下的 k 位同学排成合唱队形。
合唱队形是指这样的一种队形设 kk 位同学从左到右依次编号为 1,2, … ,k他们的身高分别为,, … ,则他们的身高满足 ………… (1≤i≤k)。
你的任务是已知所有 n 位同学的身高计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。
【输入】
共二行。
第一行是一个整数 n2≤n≤100n 表示同学的总数。
第二行有 n 个整数用空格分隔第 i 个整数 130≤ ≤230是第 i 位同学的身高厘米。
【输出】
一个整数最少需要几位同学出列。 样例输入 8 186 186 150 200 160 130 197 220 样例输出 4 解题思路
这个题目不是单纯的递增或者递减数列而是先递增再递减。
我首先想的是从1 到 n 存入身高初始化动态 dp 数组每个里面的值赋为 i-1(例如第 1 个 dp[1]0然后从 2 到 n 进行遍历代表的是递增的节制点 k然后分情况讨论内部进行两个循环一个循环对 1 至 k 进行考虑如果不满足 a[j]a[i]就重新赋值dp[i] min(dp[i],dp[j]1),但是这里要考虑一个问题是如果去掉了一个人他的编号是 x那么他的下一个人x1的身高还是和第 x 个人比较这里会有些复杂 dp 数组里面更新的最小值是从哪一个人开始更新的说明这个人不用考虑可能还需要用一个值存储更新的这个人的前一个人的身高。这是计算递增情况的然后递减情况类似。
然后我看了下题解他们的思路都很像是先用两层循环目的是从第 1 个人到第 n 个人找对应下标的最大升序列再用两层循环从第 n 个人到第 1 个人找对应下标的最大升序列。
题目不就是要找前一部分是升序后一段是从后往前的升序嘛那将两个升序对应的下标的值相加注意要减一因为前一段和后一段的中间那个数计算了两次。
然后计算上的人数就是符合要求的要求的是去除的人数就用 n-max max是统计人数时出现的最大值。
先用代码解决找升序的问题
for(i1;in;i)//从左到右找递增的个数 {for(j0;ji;j){if(a[j]a[i])b[i]max(b[i],b[j]1);} }
不过要注意的是尽管数列是从第 1 个人开始数的但是内存循环的 j0 全局变量中 a[0]0,对于第一个人来说这个人肯定要入列这时 a[1]a[0]b[1]b[0]1其实也可以在初始化时就把b[1] 赋值为1也是一样的效果。 对于后一段也是同样的思路。
代码如下
#includestdio.h
int a[105];
int b[105],c[105],sum;
int max(int x,int y)
{if(xy)return y;elsereturn x;
}
int main()
{int n,i,j;scanf(%d,n);for(i1;in;i){scanf(%d,a[i]);}for(i1;in;i)//从左到右找递增的个数 {for(j0;ji;j){if(a[j]a[i])b[i]max(b[i],b[j]1);} }for(in;i0;i--)//从左往右找递减的个数 {for(jn1;ji;j--){if(a[i]a[j])c[i]max(c[i],c[j]1);}}for(i1;in;i)summax(sum,c[i]b[i]-1);//找中途出现的最大值 printf(%d,n-sum);return 0;
}
