【SSL_1041】2004年分区联赛提高组之三 合唱队形
日期: 2020-08-20 分类: 跨站数据测试 234次阅读
合唱队形
Time Limit:1000MS Memory Limit:65536K
Total Submit:253 Accepted:111
题目
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,
他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1<…Ti+1>…>TK(1<=i<=K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,
可以使得剩下的同学排成合唱队形。
Input
输入的第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,
第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
Output
输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
Sample Input
8
186 186 150 200 160 130 197 220
Sample Output
4
Hint
对于50%的数据,保证有n<=20;
对于全部的数据,保证有n<=100。
解题思路
题意是出列最少的人,使得剩下的人符合身高递增然后递减的规则。
可以先枚举中间最高的那个人,从1到最高者求最长不下降序列长度,
再从最高者到n求最长不上升序列长度,最后加起来并算出最少需出列几人。
最长不下降序列 f[i]=max(f[i+1],f[i+2]······f[k])+1, a[i]<a[j] ,k-1>=i>=1, i+1<=j<=k
最长不上升序列 f[i]=max(f[i+1],f[i+2]······f[n])+1, a[i]>a[j] ,n-1>=i>=k, i+1<=j<=n
代码
#include<cstring>
#include<iostream>
using namespace std;
int n,m,a[10001],f[10001],c,ans=100000;
void in(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
}int DP(int k){
int au=0;
memset(f,0,sizeof(f));//一定要初始化
f[k]=1;
for(int i=k-1;i>0;i--){
c=0;
for(int j=i+1;j<=k;j++){
if(a[i]<a[j]){
if(f[j]>c){
c=f[j];
}
}
}f[i]=c+1;
}for(int i=1;i<=n;i++){
au=max(au,f[i]);
}return k-au;//返回前i个人最小需出列数
}int DPd(int k){
int au=0;
memset(f,0,sizeof(f));//一定要初始化
f[n]=1;
for(int i=n-1;i>=k;i--){
c=0;
for(int j=i+1;j<=n;j++){
if(a[i]>a[j]){
if(f[j]>c){
c=f[j];
}
}
}f[i]=c+1;
}for(int i=k;i<=n;i++){
au=max(au,f[i]);
}return n-k-au;//返回后i个人最小需出列数
}
void out(){
cout<<ans;
}
int main(){
in();
for(int i=1;i<=n;i++){//枚举中间最高的人
int x=DP(i),y=DPd(i);
ans=min(x+y+1,ans);//最小出列数
}out();
}
除特别声明,本站所有文章均为原创,如需转载请以超级链接形式注明出处:SmartCat's Blog
标签:动态规划 动态规划 算法
上一篇: 【SSL_1276】石子归并 (DP)
下一篇: git比较远程仓库和本地仓库之间的差异
精华推荐