题解 | #合唱队#
合唱队
http://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
#include <iostream> //#include <algrithm> using namespace std; int max(int a, int b) { if(a>=b) { return a; } return b; } int main() { int num; while(cin>>num) { //shu ru int input[num], dpl[num],dpr[num]; for(int i=0; i<num; i++) { cin>>input[i]; } //left for(int i=0; i<num; i++) { dpl[i] = 1; for(int j = 0; j<i; j++) { if(input[i]>input[j]) { dpl[i] = max(dpl[i],dpl[j]+1); } } } //righjt for(int i=num-1; i>=0; i--) { dpr[i] = 1; for(int j=num - 1; j>=i; j--) { if(input[i]>input[j]) { dpr[i] = max(dpr[j]+1,dpr[i]); } } } int result = 0; for(int i=0; i<num; i++) { result = max(result, dpl[i]+dpr[i]-1); } cout<<num-result<<endl; } }