P1091 [NOIP2004 提高组] 合唱队形
本题链接：P1091 [NOIP2004 提高组] 合唱队形
本博客给出本题截图：
AC代码
代码解释：看成一个上升子序列 + 一个下降子序列，f[i]表示以i为结尾的最长上升子序列，g[i]表示以i为开头的最长下降自序列，本题问最少需要几名同学出列，其实就是问出列后队伍最长是多长，即我们需要求一个上升子序列和一个下降子序列，使得这两个子序列的长度和最长，即求max(f[i] + g[i] - 1)，-1的原因是因为i这个位置算了两次，然后就变成了一个简单的 LIS问题.
代码*：
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int f[N], g[N]; int n; int h[N]; int main() { cin >> n; for (int i = 1; i <= n; i ++ ) cin >> h[i]; for (int i = 1; i <= n; i ++ ) { f[i] = 1; for (int j = 1; j < i; j ++ ) if (h[j] < h[i]) f[i] = max(f[i], f[j] + 1); } for (int i = n; i; i -- ) { g[i] = 1; for (int j = n; j > i; j -- ) if (h[j] < h[i]) g[i] = max(g[i], g[j] + 1); } int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1); cout << n - res << endl; return 0; }
