1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1
：怪盗基德的滑翔翼。有N个数，表示房屋的高度，你可以任意选择一个房屋作为起点，选择朝左飞，或者朝右飞，必须严格递减才能够飞到下一个房屋，求经过的最大房屋数。
解题思路：DP，参考最长上升子序列的模型。需要注意的是，本题目可以选择朝左飞，因此除了正着求一遍单调下降子序列，也需要逆着求一遍单调下降子序列（这个等价于正着求一遍单调上升子序列）。
C++代码如下，
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int a[N];
int f[N];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
int res = 0;
//正着求一遍单调下降子序列
for (int i = 1; i <= n; ++i) {
f[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] > a[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
//正着求一遍单调上升子序列
memset(f, 0, sizeof f);
for (int i = 1; i <= n; ++i) {
f[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] < a[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
cout << res << endl;
}
return 0;
}
题目2
：登山。给你N个数，表示山峰的高度，你必须先严格上升，然后严格下降，求最多观光的山峰数目。
解题思路：DP，最长上升子序列。以a[i]为起点的严格下降等价于从右往左的以a[i]为终点的严格上升。两遍DP，然后最终答案等于f[i] + g[i] - 1的最大值。
C++代码如下，
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N], g[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
//求以a[i]为结尾的单调上升子序列
for (int i = 1; i <= n; ++i) {
f[i] = 1;
for (int j = 1; j < i; ++j) {
if (a[j] < a[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
//求以a[i]为结尾的单调上升子序列，从右往左
for (int i = n; i >= 0; --i) {
g[i] = 1;
for (int j = n; j > i; --j) {
if (a[i] > a[j]) {
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 << res << endl;
return 0;
}
题目3
：合唱队形。
解题思路：同题目2登山。只不过答案是n - max(f[i] + g[i] - 1)。
C++代码如下，
#include <iostream>
using namespace std;
const int N = 110;
int n;
int a[N];
int f[N];
int g[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
//正着求一遍单调上升
for (int i = 1; i <= n; ++i) {
f[i] = 1;
for (int j = 0; j < i; ++j) {
if (a[j] < a[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
//逆着求一遍单调上升
for (int i = n; i >= 0; --i) {
g[i] = 1;
for (int j = n; j > i; --j) {
if (a[i] > a[j]) {
g[i] = max(g[i], g[j] + 1);
}
}
}
//求最大的f[i]+g[i]-1
int ans = 0;
for (int i = 1; i <= n; ++i) ans = max(ans, f[i] + g[i] - 1);
cout << n - ans << endl;
return 0;
}
题目4
：友好城市。
解题思路：按照某个城市排序，然后在另一个城市当中计算最长上升子序列。
C++代码如下，
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5010;
int n;
vector<pair<int,int>> vec;
int f[N];
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
vec.emplace_back(a,b);
}
sort(vec.begin(), vec.end());
int res = 0;
for (int i = 0; i < n; ++i) {
f[i] = 1;
for (int j = 0; j < i; ++j) {
if (vec[i].second > vec[j].second) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
题目5
：最大上升子序列的和。给你N个数，问所有上升子序列中和的最大值是多少？
解题思路：DP，最长上升子序列模型。
状态定义
f[i]
：以第i个元素结尾的上升子序列的最大和。
状态转移，求以下情况的最大值：
-
该子序列只有a[i]一个元素，即
a[i]
。
-
如果
a[1] < a[i]
，那么有
f[1] + a[i]
。
-
如果
a[2] < a[i]
，那么有
f[2] + a[i]
。
-
……
-
如果
a[i-1] < a[i]
，那么有
f[i-1] + a[i]
。
C++代码如下，
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
int res = 0;
for (int i = 1; i <= n; ++i) {
f[i] = a[i];
for (int j = 1; j < i; ++j) {
if (a[j] < a[i]) {
f[i] = max(f[i], f[j] + a[i]);
}
}
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
