DPコーラス隊形


タイトルの説明
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<