DPコーラス隊形
2646 ワード
タイトルの説明
N人の学生が一列に並んで、音楽の先生はその中の(N-K)人の学生に列を作ってもらって、残りのK人の学生が合唱の隊形に並ぶようにします.
合唱隊形とは、K人の同級生を左から右に順に1,2...,Kとし、彼らの身長はそれぞれT 1,T 2,...,TKであれば、彼らの身長はT 1<...>を満たす隊形である.Ti+1>…>TK(1<=i<=K).
あなたの任務は、すべてのN人の同級生の身長を知っていて、少なくとも何人の同級生が列に並ぶ必要があることを計算して、残りの同級生を合唱の隊形に並べることができます.
にゅうしゅつりょくけいしき
入力形式:
入力ファイルinの最初の行は整数N(2<=N<=100)であり、同級生の総数を表す.1行目にはn個の整数があり、スペースで区切られ、i番目の整数Ti(130<=Ti<=230)はi番目の同級生の身長(センチメートル)である.
出力フォーマット:
出力ファイルoutには1行が含まれています.この行には1つの整数しか含まれていません.つまり、少なくとも何人かの同級生が列を出す必要があります.
入出力サンプル
入力サンプル#1:コピー
出力サンプル#1:コピー
説明
50%のデータに対して、n<=20が保証されている.
すべてのデータに対して、n<=100が保証されます.
テーマ分析:
実は2つの最長の増加シーケンス(増加)を求めます
私たちは左から右へと右から左への順序でn人の同級生を数列に並べ,どのように2つの数列の中で増加したとは限らない長男のシーケンスを求めるかが鍵となる.
aは身長シーケンスである.
bは、左から右の身長が増加する人数のシーケンスであり、b[i]は、同級生1から同級生iの身長の間で増加順序を満たす最大人数(iを含む)である.
cは右から左の身長が増加する人数のシーケンスであり、c[i]は同級生nから同級生iの身長の間で増加順序を満たす最大人数(iを含む)である.
b[i]とc[i]を最大にするには,サブ問題の解b[j].c[k]は最大でなければならない,(1<=j<=i-1,i+1<=k<=n)
出列人数はn-max(b[i]+c[i])+1(i同級生は繰り返し計算されるため、1を足す必要がある)
実装の詳細:
bとcは最長増分シーケンスに相当し、最長降下シーケンスではない
コード実装:
N人の学生が一列に並んで、音楽の先生はその中の(N-K)人の学生に列を作ってもらって、残りのK人の学生が合唱の隊形に並ぶようにします.
合唱隊形とは、K人の同級生を左から右に順に1,2...,Kとし、彼らの身長はそれぞれT 1,T 2,...,TKであれば、彼らの身長はT 1<...>を満たす隊形である.Ti+1>…>TK(1<=i<=K).
あなたの任務は、すべてのN人の同級生の身長を知っていて、少なくとも何人の同級生が列に並ぶ必要があることを計算して、残りの同級生を合唱の隊形に並べることができます.
にゅうしゅつりょくけいしき
入力形式:
入力ファイルinの最初の行は整数N(2<=N<=100)であり、同級生の総数を表す.1行目にはn個の整数があり、スペースで区切られ、i番目の整数Ti(130<=Ti<=230)はi番目の同級生の身長(センチメートル)である.
出力フォーマット:
出力ファイルoutには1行が含まれています.この行には1つの整数しか含まれていません.つまり、少なくとも何人かの同級生が列を出す必要があります.
入出力サンプル
入力サンプル#1:コピー
8
186 186 150 200 160 130 197 220
出力サンプル#1:コピー
4
説明
50%のデータに対して、n<=20が保証されている.
すべてのデータに対して、n<=100が保証されます.
テーマ分析:
実は2つの最長の増加シーケンス(増加)を求めます
私たちは左から右へと右から左への順序でn人の同級生を数列に並べ,どのように2つの数列の中で増加したとは限らない長男のシーケンスを求めるかが鍵となる.
aは身長シーケンスである.
bは、左から右の身長が増加する人数のシーケンスであり、b[i]は、同級生1から同級生iの身長の間で増加順序を満たす最大人数(iを含む)である.
cは右から左の身長が増加する人数のシーケンスであり、c[i]は同級生nから同級生iの身長の間で増加順序を満たす最大人数(iを含む)である.
b[i]とc[i]を最大にするには,サブ問題の解b[j].c[k]は最大でなければならない,(1<=j<=i-1,i+1<=k<=n)
出列人数はn-max(b[i]+c[i])+1(i同級生は繰り返し計算されるため、1を足す必要がある)
実装の詳細:
bとcは最長増分シーケンスに相当し、最長降下シーケンスではない
コード実装:
#include
using namespace std;
const int maxn=1005;
int a[maxn],i,j,k,maxx,c[maxn],b[maxn];
int main()
{
int n;
cin>>n;
for(i=1;i<=n;i++)
{
b[i]=1;
c[i]=1;
cin>>a[i];
}
for(i=1;i<=n;i++)
{
maxx=0;
for(j=1;j<=i-1;j++)
if(a[j]maxx)
maxx=b[j];
if(maxx>0)
{
b[i]=maxx+1;
}
}
for(i=n;i>=1;i--)
{
maxx=0;
for(j=i+1;j<=n;j++)
if(a[j]maxx)
maxx=c[j];
if(maxx>0)
{
c[i]=maxx+1;
}
}
maxx=0;
for(i=1;i<=n;i++)
maxx=max(maxx,b[i]+c[i]);
cout<
#include
using namespace std;
int main()
{
int i,j,n,a[200],b[200],c[200];
cin>>n;
for(i=0;i>a[i];
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(i=0;ia[j]&&b[j]+1>b[i])
{
b[i]=b[j]+1;}
}
}
for(i=n-1;i>=0;i--)
{
c[i]=1;
for(j=i+1;ja[j])
c[i]=c[j]+1;
}
}
int max=0;
for(i=0;imax)
max=b[i]+c[i];
cout<