房地产做网站怎样吸引客户,广东哪有做网赌网站,wordpress 二级菜单样式,天涯重庆论坛题干#xff1a;
N位同学站成一排#xff0c;音乐老师要请其中的(N-K)位同学出列#xff0c;使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形#xff1a;设K位同学从左到右依次编号为1, 2, …, K#xff0c;他们的身高分别为T1, T2, …, TK
N位同学站成一排音乐老师要请其中的(N-K)位同学出列使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形设K位同学从左到右依次编号为1, 2, …, K他们的身高分别为T1, T2, …, TK则他们的身高满足T1 T2 … Ti , Ti Ti1 … TK (1 i K)。 你的任务是已知所有N位同学的身高计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。
Input
输入的第一行是一个整数N2 N 100表示同学的总数。第一行有n个整数用空格分隔第i个整数Ti130 Ti 230是第i位同学的身高厘米。
Output
输出包括一行这一行只包含一个整数就是最少需要几位同学出列。
Sample Input
8
186 186 150 200 160 130 197 220Sample Output
4
解题报告 从左到右求一个lis从右向左求一个lis然后枚举中间顶点就可以了。
AC代码
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int a[1000 5];
int dp[2000 5];
int rdp[2000 5];
/可以用二分优化。
int main()
{int n;cinn;for(int i 1; in; i) {cina[i];dp[i] 1;rdp[i] 1;}for(int i 1; in; i) {for(int j 1; ji; j) {if(a[i] a[j]) dp[i] max(dp[i],dp[j] 1);}}for(int i n; i1; i--) {for(int j n; ji; j--) {if(a[i] a[j]) rdp[i] max(rdp[i],rdp[j] 1);}} int minn n;for(int i 1; in; i) {minn min(i - dp[i] (n-i1) - rdp[i],minn);}cout minn endl;return 0 ;
}
总结 注意dp[i]求的是截止到第i位的所以包括了i这一位这也是为什么初始化为1而不是0的原因所以你在求minn的时候注意右边那一部分需要(n-i1)而不是(n-i)
