本文共 1934 字，大约阅读时间需要 6 分钟。
**题意：删去最少的人，使得任何一个人能看到左右 任一 一边的尽头。
思路：从左边找一个最长上升子序列，从右边找一个最长上升子序列。这样两个序列 不交叉 的时候， 使得序列和最大即可。**提供两种AC代码。不懂代码的请看这道题
#include#include #include using namespace std;int dp1[1010], dp2[1010];double a[1010];int main(){ int N; while (cin >> N) { int pre=0, post=0; for (int i = 0; i < N; i++) scanf("%f", &a[i]); for (int i = 0; i < N; i++) { dp1[i] = 1; for (int j = 0; j < i; j++) if (a[i] > a[j]) dp1[i] = max(dp1[i], dp1[j]+1); pre = max(pre, dp1[i]); } for (int i = N-1; i >=0; i--) { dp2[i] = 1; for (int j = N-1; j > i; j--) if (a[i] > a[j]) dp2[i] = max(dp2[i], dp2[j]+1); post = max(post, dp2[i]); } int Max = 0; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) Max = max(Max,dp1[i] +dp2[j]); cout << N - Max << endl; }}
#include#include #include const float INF =1e6;using namespace std;double dp1[1010], dp2[1010]; //不要忘记修改为浮点型哦！double a[1010];int ans1[1010], ans2[1010]; //这个里面存放前后最长上升序列的长度。int main(){ int N; while (cin >> N) { for (int i = 0; i < N; i++) scanf("%f", &a[i]); fill(dp1, dp1 + N, INF); for (int i = 0; i < N; i++) { *lower_bound(dp1, dp1 + N, a[i]) = a[i]; ans1[i] = lower_bound(dp1, dp1 + N, INF) - dp1; } fill(dp2, dp2 + N, INF); for (int i = N-1; i >=0; i--) { *lower_bound(dp2, dp2 + N, a[i]) = a[i]; ans2[i] = lower_bound(dp2, dp2 + N, INF) - dp2; } int Max = 0; for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) Max = max(Max,ans1[i] +ans2[j]); cout << N - Max << endl; }}
转载地址：http://qkyci.baihongyu.com/