【NKs 1042】合唱隊形
1745 ワード
合唱隊形(NOIP)
Time Limit:1000MS Memory Limit:65536K Total Submit:314 Accepted:139
Description
N人の学生が一列に並んで、音楽の先生はその中の(N-K)人の学生に列を作ってもらって、残りのK人の学生が合唱の隊形に並ぶようにします.合唱隊形とは、K人の同級生を左から右に順に1,2...,Kとし、彼らの身長をT 1,T 2,...,TKとすると、彼らの身長はT 1<...Ti+1>…>TK,(1<=i<=K).あなたの任務は、すべてのN人の同級生の身長を知っていて、少なくとも何人の同級生が列に並ぶ必要があることを計算して、残りの同級生を合唱の隊形に並べることができます.
Input
入力された最初の行は整数N(2<=N<=100)であり、同級生の総数を表す.1行目にはn個の整数があり、スペースで区切られ、i番目の整数Ti(130<=Ti<=230)はi番目の同級生の身長(センチメートル)である.
Output
出力には1行が含まれています.この行には1つの整数しか含まれていません.つまり、少なくとも何人かの学生が列を出す必要があります.
Sample Input
Sample Output
Source
NOIP2004
【分析】
Tiの前面は上昇子配列であり,背面は下降子配列であり,問題は最長上昇子配列と最長下低下子配列を探すことに分解できることは明らかである.行列を反転させて最長上昇サブシーケンスを求めることで最長下降サブシーケンスを求め,最後に総人数を最も多くするTiを探すことが容易に考えられる.
【ACコード】
Time Limit:1000MS Memory Limit:65536K Total Submit:314 Accepted:139
Description
N人の学生が一列に並んで、音楽の先生はその中の(N-K)人の学生に列を作ってもらって、残りのK人の学生が合唱の隊形に並ぶようにします.合唱隊形とは、K人の同級生を左から右に順に1,2...,Kとし、彼らの身長をT 1,T 2,...,TKとすると、彼らの身長はT 1<...
Input
入力された最初の行は整数N(2<=N<=100)であり、同級生の総数を表す.1行目にはn個の整数があり、スペースで区切られ、i番目の整数Ti(130<=Ti<=230)はi番目の同級生の身長(センチメートル)である.
Output
出力には1行が含まれています.この行には1つの整数しか含まれていません.つまり、少なくとも何人かの学生が列を出す必要があります.
Sample Input
8 186 186 150 200 160 130 197 220 Sample Output
4 Source
NOIP2004
【分析】
Tiの前面は上昇子配列であり,背面は下降子配列であり,問題は最長上昇子配列と最長下低下子配列を探すことに分解できることは明らかである.行列を反転させて最長上昇サブシーケンスを求めることで最長下降サブシーケンスを求め,最後に総人数を最も多くするTiを探すことが容易に考えられる.
【ACコード】
#include<stdio.h>
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<i;j++)
{
if(u[j]<u[i]&&f[j]+1>f[i])
f[i]=f[j]+1;
}
}//
for(i=1;i<=n;i++)
{
g[i]=1;
for(j=1;j<i;j++)
{
if(d[j]<d[i]&&g[j]+1>g[i])
g[i]=g[j]+1;
}
}//
ans=f[1]+g[n];
for(i=1;i<=n;i++)
{
if(ans<f[i]+g[n+1-i])
ans=f[i]+g[n+1-i];
}
ans=ans-1; //
printf("%d",n-ans);
return 0;
}