【NKs 1042】合唱队形

2016-12-02 12:52:04来源:网络收集作者:管理员人点击

合唱队形(NOIP)


Time Limit:1000MS Memory Limit:65536K
Total Submit:314 Accepted:139


Description


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


Source


NOIP2004




【分析】


很显然,Ti前面是一个上升子序列,后面是一个下降子序列,问题可以分解为找最长上升子序列和最长下降子序列。容易想到通过将队伍反转求最长上升子序列来求最长下降子序列,最后查找使得总人数最多的Ti。




【AC代码】


#include
int main()
{
int n,i,j,f[110],g[110],u[110],d[110],ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&u[i]);
d[n+1-i]=u[i];//反转顺序用来求下降子序列
}
for(i=1;i<=n;i++)
{
f[i]=1;
for(j=1;j {
if(u[j]f[i])
f[i]=f[j]+1;
}
}//上升子序列
for(i=1;i<=n;i++)
{
g[i]=1;
for(j=1;j {
if(d[j]g[i])
g[i]=g[j]+1;
}
}//下降子序列
ans=f[1]+g[n];
for(i=1;i<=n;i++)
{
if(ans ans=f[i]+g[n+1-i];
}
ans=ans-1; //合唱队形的最大人数
printf("%d",n-ans);
return 0;
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台