JZOJsenior1168.【NOIPダイナミックプランニング特集】合唱隊形

3358 ワード

NOIP DP 雑題

problem
Description
N人の学生が一列に並んで、音楽の先生はその中の(N-K)人の学生に列を作ってもらって、残りのK人の学生が合唱の隊形に並ぶようにします.合唱隊形とは、K人の同級生を左から右に順に1,2,...,Kとし、彼らの身長をT 1,T 2,...,TKとすると、彼らの身長はT 1Ti+1>...>TK(1<=i<=K)を満たす.あなたの任務は、すべてのN人の同級生の身長を知っていて、少なくとも何人の同級生が列に並ぶ必要があることを計算して、残りの同級生を合唱の隊形に並べることができます.
Input
入力ファイルの最初の行は、同級生の総数を表す整数N(2<=N<=100)である.最初の行にはn個の整数があり、スペースで区切られ、i番目の整数Ti(130<=Ti<=230)はi番目の同級生の身長(センチメートル)である.
Output
出力ファイルには1行が含まれています.この行には1つの整数しか含まれていません.つまり、少なくとも数人の学生が列を出す必要があります.
Sample Input
8 186 186 150 200 160 130 197 220
Sample Output
4
Data Constraint
50%のデータに対して、n<=20が保証されている.すべてのデータに対して、n<=100が保証されます.
analysis
ひとつのNOIPの経典の題目、DPは解決します
2つの配列b[i]とc[i]を開き、それぞれ1~iの最長立ち上がりサブシーケンスとi~nの最長立ち下がりサブシーケンスの長さDPを2回表すと、ans[i]はn−(b[i]+c[i]−1)に等しい(i位は2回計算されるので1を減算する)最終的な答えはmax(ans[i])である
code

#include

using namespace std;

int a[101],b[101],c[101];
int n;

int max(int x,int y)
{
    return x>y?x:y;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (int i=1;i<=n;i++)
    {
        b[i]=1;
        for (int j=1;jif (a[i]>a[j] && b[j]+1>b[i])b[i]=b[j]+1;
        }
    }
    for (int i=n;i>=1;i--)
    {
        c[i]=1;
        for (int j=i+1;j<=n;j++)
        {
            if (a[i]>a[j] && c[j]+1>c[i])c[i]=c[j]+1;
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        ans=max(ans,b[i]+c[i]);
    }
    printf("%d
",n-ans+1);
    return 0;
}

React Hooks、useStateの更新関数引数には関数を

Python試験_3回目