四、AcWing 482. 合唱队形
1.题目
本题链接：合唱队形
本博客提供本题截图：
2.逻辑解释
看成一个上升子序列 + 一个下降子序列，f[i]表示以i为结尾的最长上升子序列，g[i]表示以i为开头的最长下降自序列，本题问最少需要几名同学出列，其实就是问出列后队伍最长是多长，即我们需要求一个上升子序列和一个下降子序列，使得这两个子序列的长度和最长，即求max(f[i] + g[i] - 1)，-1的原因是因为i这个位置算了两次，然后就变成了一个简单的 LIS问题.
3.AC代码
#include <iostream> #include <algorithm> using namespace std; const int N = 110; int f[N], g[N]; int h[N]; int main() { int n; 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; }
五、AcWing 1012. 友好城市
1.题目
本题链接：友好城市
本博客提供本题截图：
2.逻辑解释
本题就是造桥，每个桥有两个参数x1和x2，表示桥的一头连接在上岸坐标为x1的地方，一头连在下岸坐标为x2的地方，我们所求的为在要求桥不想交的前提下，建尽可能多的桥
以上图一中红色的就是题目中的样例，图二中蓝色的则是我们最后选择的桥梁。
我们可以按照上岸的坐标从小到大来枚举，然后我们只需关心下岸的坐标之间有何关系即可；于是，不难发现，上坐标从小到大枚举选择到的桥，其对应下坐标也必然是从小到大的.
3.AC代码
#include <iostream> #include <algorithm> #include <map> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 5010; PII h[N]; int f[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i ++ ) cin >> h[i].x >> h[i].y; sort(h, h + n); int res = 0; for (int i = 0; i < n; i ++ ) { f[i] = 1; for (int j = 0; j < n; j ++ ) if (h[j].y < h[i].y) f[i] = max(f[i], f[j] + 1); res = max(res, f[i]); } cout << res << endl; return 0; }
