题解 | #合唱队#
合唱队
http://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
合唱队:C语言解法
通过用例 6/10 卡在第二个结果,预期输出1995,实际输出1991,有没有大佬知道为什么
#include<stdio.h>
int fmax(int a, int b){
return a>b?a:b;
}
int main(){
int num = 0, max = 1;
while(~scanf("%d\n",&num)){
int dple[num];
int dpri[num];
int arr[num];
memset(dple, 0, sizeof(dple));
memset(dpri, 0, sizeof(dpri));
memset(arr, 0, sizeof(arr));
dple[0]=1,dpri[num-1]=1;
for(int i=0; i<num; i++){
scanf("%d ",&arr[i]);
}
for(int j=1; j<num; j++){
dple[j] = 1;
for(int k=j-1; k>=0; k--){
if(arr[j]>arr[k]){
dple[j] = fmax(dple[j], dple[k]+1);
}
}
}
for(int m=num-2; m>=0; m--){
dpri[m] = 1;
for(int n=m+1; n<num; n++){
if(arr[m]>arr[n]){
dpri[m] = fmax(dpri[m], dpri[n]+1);
}
}
}
for(int a=0; a<num; a++){
dple[a]+=(dpri[a]-1);
max = fmax(dple[a], max);
}
printf("%d\n",num-max);
}
}