AC日记——合唱队形 洛谷 P1901
2024-09-07 03:45:28
题目描述
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入输出格式
输入格式：
输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出格式：
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
输入输出样例
输入样例#1：
8
186 186 150 200 160 130 197 220
输出样例#1：
4
说明
对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。
思路：
正反两遍lcs，然后每举断点取最优；
来，上代码：
#include <cstdio>
#include <iostream> using namespace std; int n,ai[],dp[],dp_[],ans; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&ai[i]);
for(int i=;i<=n;i++)
{
for(int j=;j<i;j++)
{
if(ai[i]>ai[j]) dp[i]=max(dp[i],dp[j]+);
}
}
for(int i=n;i>=;i--)
{
for(int j=n;j>i;j--)
{
if(ai[i]>ai[j]) dp_[i]=max(dp_[i],dp_[j]+);
}
}
for(int i=;i<=n;i++)
{
ans=max(ans,dp[i]+dp_[i]+);
}
printf("%d\n",n-ans);
return ;
}
最新文章
- Python之路【第十七篇】Django进阶篇
- [转载]javascript创建对象的几种方式
- Velocity(6)——#if指令
- Java：String和Date、Timestamp之间的转换
- Httpservlet cannot be resolved to a type的原因与解决方法
- Sunglasses
- Debug模式应用程序输出Debug调试信息（现成的宏定义，用于格式化打印信息）
- view中的setTag和getTag方法的理解
- SubLime BracketHighlighter 配置
- vcs 下使用system verilog调用c函数
- 功能强大的HTML
- log4j输出到指定日志文件
- APC注入
- 从源码安装go 1.2.2
- C#中简单操作SQLserver数据库（ADO.NET的简单应用）
- Java实现二叉树的前序、中序、后序、层序遍历（递归方法）
- Nginx详解二十七：Nginx架构篇之安全篇
- Checkbox: ListView 与CheckBox 触发事件冲突的问题
- 【Spring源码深度解析学习系列】Bean的加载（六）
- 机器学习数学知识中令人费解的notation符号注解