【问题描述】
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <stdio.h> #include <string.h> #define MAXN 200 int main() { int n, a[MAXN], b[MAXN], c[MAXN], i, j, max; scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); memset(b, 0, sizeof(a)); memset(c, 0, sizeof(c)); b[1] = 1; for (i = 2; i <= n; i++) { max = 0; for (j = i - 1; j >= 1; j--) { if (a[j] < a[i] && b[j] + 1 > max) max = b[j]; } b[i] = max + 1; } c[n] = 1; for (i = n - 1; i > 0; i--) { max = 0; for (j = i + 1; j <= n; j++) { if (a[j] < a[i] && c[j] + 1 > max) max = c[j]; } c[i] = max + 1; } max = b[1] + c[1]; for (i = 2; i <= n; i++) { if (b[i] + c[i] > max) max = b[i] + c[i]; } printf("%d\n", n - max + 1); return 0; } |