爱华网再写DP，是一道经典中的经典。
中文题，不解释了。可参考RQNOJ-26 和TYVJ-1067。
题解：分别设f[i]和g[i]表示为：
第i个以前的最长上升序列数和第i个以后的最长下降序列数。
然后枚举k，答案就是Min (n-(f[k]+g[k]-1))
也就是，第k个点的左右之和的最大值减去重复的自己，取用最大值是因为存活人数最多，踢掉人数最少。
不罗嗦了，看代码，我喜欢的就是Max函数，我只用一个，利用函数的tmp参数来表示。
代码：
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
intheight[105], n;
int Max(int array[105], int left, int right, int tmp) {
int i, max =0, k = tmp == 1 ? right : left;
for (i =left; i <= right; i++) {
if (height[i] >= height[k] || array[i] == 0)
continue;
max = max < array[i] ? array[i] : max;
}
returnmax;
}
int dp(int now) {
intf[now+1], g[now+1], i, max = 0;
memset (f,0, sizeof (f));
memset (g,0, sizeof (g));
f[1] =1;
for (i = 2;i <= now; i++)
f[i] = Max (f, 1, i, 1) + 1;
g[n] =1;
for (i =n-1; i >= 1; i--)
g[i] = Max (g, i, n, -1) + 1;
for (i = 1;i <= n; i++)
if (max < f[i]+g[i]-1)
max = f[i]+g[i]-1;
returnmax;
}
int main () {
int i;
scanf ("%d",&n);
for (i = 1;i <= n; i++)
scanf ("%d", &height[i]);
printf("%d", n - dp (n));
//system("pause");
return0;
}
For NOIP, Fighting !
