P1091 [NOIP2004 提高组] 合唱队形
2024-09-07 13:41:53
题目描述
$N$位同学站成一排,音乐老师要请其中的$\left ( N-K\right )$位同学出列,使得剩下的$K$位同学排成合唱队形。
合唱队形是指这样的一种队形:设$K$位同学从左到右依次编号为$1,2,...,K$,他们的身高分别为$T_{1},T_{2},...,T_{K}$, 则他们的身高满足$T_{1}< ...<T_{i}>T_{i+1}>...>T_{K}\left ( 1\leqslant i\leqslant K\right )$。
你的任务是,已知所有$N$位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入格式
共二行。
第一行是一个整数$N\left ( 2\leqslant N\leqslant 100\right )$,表示同学的总数。
第二行有$N$个整数,用空格分隔,第$i$个整数$T_{i}\left ( 130\leqslant T_{i}\leqslant 230\right )$是第$i$位同学的身高(厘米)。
输出格式
一个整数,最少需要几位同学出列。
样例数据
输入
8
186 186 150 200 160 130 197 220
输出
4
分析
根据题目信息,可将题目翻译为:在一组数据中找到除最长不下降子序列与最长不上升子序列以外的数的个数
$Dp_{i}$表示从$1$到$i$的最长不下降子序列的长度,至于最长不上升的子序列长度求法,就是循环倒过来,继续求最长不下降子序列长度
$Dp\underline{ }UP$表示$T_{i}$之前序列长度,$Dp\underline{ }DOWN$表示$T_{i}$之后的序列长度
状态转移方程
代码
#include <bits/stdc++.h> #define Enter puts("")
#define Space putchar(' ') using namespace std; typedef long long ll;
typedef double Db; inline ll Read()
{
ll Ans = 0;
char Ch = getchar() , Las = ' ';
while(!isdigit(Ch))
{
Las = Ch;
Ch = getchar();
}
while(isdigit(Ch))
{
Ans = (Ans << 3) + (Ans << 1) + Ch - '0';
Ch = getchar();
}
if(Las == '-')
Ans = -Ans;
return Ans;
} inline void Write(ll x)
{
if(x < 0)
{
x = -x;
putchar('-');
}
if(x >= 10)
Write(x / 10);
putchar(x % 10 + '0');
} int T[100001];
int Dp_UP[100001];
int Dp_DOWN[100001];
int Ans; int main()
{
int n;
n = Read();
for(int i = 1; i <= n; i++)
T[i] = Read();
T[0] = 0;
for(int i = 1; i <= n; i++)
for(int j = 0; j < i; j++)
if(T[i] > T[j])
Dp_UP[i] = max(Dp_UP[i] , Dp_UP[j]+1);
T[n + 1] = 0;
for(int i = n; i > 0; i--)
for(int j = n + 1; j > i; j--)
if(T[i] > T[j])
Dp_DOWN[i] = max(Dp_DOWN[i] , Dp_DOWN[j] + 1);
for(int i = 1; i <= n; i++)
Ans = max(Dp_UP[i] + Dp_DOWN[i] - 1, Ans);
Write(n - Ans);
return 0;
}
最新文章
- .NET+IIS+MSSQL配置
- Atitit webservice的发现机制 discover机制
- 使用Angular2理由
- 20145213《Java程序设计》第五周学习总结补充
- jsp学习(三)
- C++ CreateDirectory
- Arrays.sort(new String[]{";aaa";}); 排序方法
- Children&#39;s Day
- Linux查看端口号
- python中的类属性和实例属性
- Python学习笔记(四)
- jsp内置对象 的使用范围和类型【说明】
- Intellij IDEA插件开发入门
- javascript项目实战---ajax实现无刷新分页
- html5 拖拽上传文件时,屏蔽浏览器默认打开文件
- c选择排序算法
- angular笔记_10
- bfs记录路径,蓝桥杯真题
- 小白的CTF学习之路2——二进制数据基础与运算(上)
- [Algorithm] Check for balanced parentheses using stack