夕食の列の手配‖(面倒な会食)
9024 ワード
説明
レストランの混雑を避けるため、FJは乳牛たちに33回に分けて食事をするように要求した.毎日夕食前、乳牛たちはレストランの前に並んで入り、FJの想定では33回目の乳牛が列の尾に並び、列の先端は1回目の食事に設定された乳牛が占め、真ん中の位置は22回目の食事に設定された乳牛になった.乳牛たちがFJの手配を理解していないため、夕食前の行列が大迷惑になった.
第ii頭の乳牛は彼女の食事のロットDを明記している.i(1le D_ile 3)D i(1≦D i≦3)のカード.すべてのN(1le Nle 30000)N(1≦N≦30000)頭の乳牛が整然と並んでいますが、誰もがカードの番号が完全に雑然としていることがわかります.
何度も混乱して並び直した後、FJは簡単な方法を見つけた:乳牛たちは動かず、彼は列に沿って最初から最後まで歩いて、彼が列を間違えたと思っている乳牛カードの番号を変えて、最終的に彼が望んでいる各グループの乳牛が一緒に立っている列、例えば111222333あるいは333222111を手に入れた.ああ、あなたも発見しました.FJは前後逆の列に反対しません.そうすれば、すべての乳牛を後ろに回して、正常な順序でレストランに入ることができます.
あなたも知っています.FJは怠け者です.彼は目的を達成したいなら、少なくともどのくらいの乳牛カードの番号を変更しなければならないか知りたいと思っています.すべての乳牛はFJでカード番号を変更するとき、位置を移動しません.
入力
11行目:11個の整数:NN第2dots N+12...N+1行目:i+1 i+1行目は11個の整数で、i頭乳牛の食事ロットD_iD i
しゅつりょく
11行目:11個の整数を出力し、FJのために少なくとも数頭の乳牛カードの番号を変更してこそ、番号を彼の想定通りにすることができる.
まず基本コードを入力します.ここでは省略します.
レストランの混雑を避けるため、FJは乳牛たちに33回に分けて食事をするように要求した.毎日夕食前、乳牛たちはレストランの前に並んで入り、FJの想定では33回目の乳牛が列の尾に並び、列の先端は1回目の食事に設定された乳牛が占め、真ん中の位置は22回目の食事に設定された乳牛になった.乳牛たちがFJの手配を理解していないため、夕食前の行列が大迷惑になった.
第ii頭の乳牛は彼女の食事のロットDを明記している.i(1le D_ile 3)D i(1≦D i≦3)のカード.すべてのN(1le Nle 30000)N(1≦N≦30000)頭の乳牛が整然と並んでいますが、誰もがカードの番号が完全に雑然としていることがわかります.
何度も混乱して並び直した後、FJは簡単な方法を見つけた:乳牛たちは動かず、彼は列に沿って最初から最後まで歩いて、彼が列を間違えたと思っている乳牛カードの番号を変えて、最終的に彼が望んでいる各グループの乳牛が一緒に立っている列、例えば111222333あるいは333222111を手に入れた.ああ、あなたも発見しました.FJは前後逆の列に反対しません.そうすれば、すべての乳牛を後ろに回して、正常な順序でレストランに入ることができます.
あなたも知っています.FJは怠け者です.彼は目的を達成したいなら、少なくともどのくらいの乳牛カードの番号を変更しなければならないか知りたいと思っています.すべての乳牛はFJでカード番号を変更するとき、位置を移動しません.
入力
11行目:11個の整数:NN第2dots N+12...N+1行目:i+1 i+1行目は11個の整数で、i頭乳牛の食事ロットD_iD i
しゅつりょく
11行目:11個の整数を出力し、FJのために少なくとも数頭の乳牛カードの番号を変更してこそ、番号を彼の想定通りにすることができる.
まず基本コードを入力します.ここでは省略します.
#include
using namespace std;
int n,ans,sum;
int a[100010],F[100010],tmp[100010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
F[i]=1;
for(int j=i-1;j>=1&&j>=F[i];j--){
if(a[j]<=a[i]){
F[i]=max(F[i],F[j]+1);
}
ans=max(ans,F[i]);
}
}
for(int i=1;i<=n;i++){
tmp[i]=1;
for(int j=i-1;j>=1&&j>=tmp[i];j--){
if(a[j]>=a[i]){
tmp[i]=max(tmp[i],tmp[j]+1);
}
sum=max(sum,tmp[i]);
}
}
printf("%d",n-max(ans,sum));
return 0;
}