NOIP 2004 合唱队形
2024-08-27 13:33:27
洛谷 P1091 合唱队形
https://www.luogu.org/problemnew/show/P1091
JDOJ 1271: [NOIP2004]合唱队形 T3
https://neooj.com/oldoj/problem.php?id=1271
题目描述
NN位同学站成一排,音乐老师要请其中的(N-KN−K)位同学出列,使得剩下的KK位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2,…,K1,2,…,K,他们的身高分别为T_1,T_2,…,T_KT1,T2,…,TK, 则他们的身高满足T_1<...<T_i>T_{i+1}>…>T_K(1 \le i \le K)T1<...<Ti>Ti+1>…>TK(1≤i≤K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入输出格式
输入格式:
共二行。
第一行是一个整数N(2 \le N \le 100)N(2≤N≤100),表示同学的总数。
第二行有nn个整数,用空格分隔,第ii个整数T_i(130 \le T_i \le 230)Ti(130≤Ti≤230)是第ii位同学的身高(厘米)。
输出格式:
一个整数,最少需要几位同学出列。
输入输出样例
说明
对于50%的数据,保证有n \le 20n≤20;
对于全部的数据,保证有n \le 100n≤100。
动态规划基础题,需要有求最长不降子序列的基础,然后思路就比较好想了。
我们先预处理两个数组,一个从前往后存以i结尾的最长不下降序列长度,一个从后往前存以i结尾的最长不上升序列长度。
最后枚举每个人当“山峰”,求出最长序列即可。
代码:
#include<bits/stdc++.h>
using namespace std;
int t[],a[],b[];
int n,ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&t[i]);
for(int i=;i<=n;i++)
{
a[i]=;
for(int j=;j<i;j++)
{
if(t[i]>t[j] && a[j]+>a[i])
a[i]=a[j]+;
}
}
for(int i=n;i>=;i--)
{
b[i]=;
for(int j=n;j>i;j--)
{
if(t[i]>t[j] && b[j]+>b[i])
b[i]=b[j]+;
}
}
for(int i=;i<=n;i++)
{
if(b[i]+a[i]->ans)
ans=a[i]+b[i]-;
}
printf("%d",n-ans);
return ;
}
最新文章
- LRU implement Data Structure analysis
- Sass开发环境搭建
- 计算机中数据实体和数据表示形式(以C#为例)
- WorldChat.lua --世界聊天
- C#-Windows服務以LocalSystem賬戶安裝的話無法獲取我的文檔路徑
- STL中的lower_bound和upper_bound的理解
- C# zip压缩
- snowflake算法(java版)
- Spring处理id相同的bean
- LA - 4043 - Ants
- Python中的选择排序
- MySQL聚集索引和非聚集索引
- 在做自动化测试之前你需要知道的,转自:http://www.cnblogs.com/fnng/p/3653793.html
- 移动开发day2_css预处理器_flex布局
- 一起学爬虫——使用selenium和pyquery爬取京东商品列表
- eclipse添加mybatis插件
- Mask RCNN 简单使用
- Linux-Ubuntu16.0.4相关命令
- SCCM2012理论知识详解
- 小程序41028 form_id无效