vijos1098:合唱队形
2024-08-26 09:18:21
描述
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
格式
输入格式
输入的第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出格式
输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=;
int dp[][MAXN];
int h[MAXN],n;
int main()
{
cin>>n;
for(int i=;i<n;i++)
cin>>h[i];
for(int i=;i<n;i++)
{
dp[][i]=;
for(int j=;j<i;j++)
{
if(h[j]<h[i])
{
dp[][i]=max(dp[][i],dp[][j]+);
}
}
}
for(int i=n-;i>=;i--)
{
dp[][i]=;
for(int j=n-;j>i;j--)
{
if(h[i]>h[j])
{
dp[][i]=max(dp[][i],dp[][j]+);
}
}
}
int res=;
for(int k=;k<n;k++)
{
int mx1=,mx2=;
for(int i=;i<=k;i++)
{
mx1=max(dp[][i],mx1);
}
for(int i=n-;i>k;i--)
{
mx2=max(dp[][i],mx2);
}
res=max(res,mx1+mx2);
}
cout<<n-res<<endl;
return ;
}
最新文章
- vue-cli构建vue项目
- yum源的搭建
- java.sql.SQLException: Incorrect string value:
- NPOI操作Excel导入DataTable中
- wifi,网关相关标识的获取
- python-unicode十进制数字转中文
- 用Eclipse+ADT创建可运行项目,创建lib项目,引用一个lib项目
- css实现鼠标移上去变大,旋转,转别人的额
- 提高duilib的richedit控制的一些特征
- iSwifting社区【www.iSwifting.com】招聘版主
- Love myself...
- 三大框架之hibernate
- bigdecimal更精确的浮点处理方式
- (二)Java数组特性总结,你真的了解数组吗?
- 20165234 《Java程序设计》第四周学习总结
- C#中用HttpWebRequest中发送GET/HTTP/HTTPS请求 (转载)
- directive例子1
- filebeat+ELK日志系统
- duilib 修复Text控件无法设置宽度的bug,增加自动加算宽度的属性
- [Spring Data JPA问题]Executing an update/delete query; nested exception is javax.persistence.TransactionRequiredException