895. 最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
const int N = 1010;

int f[N];
int a[N];
int 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 k = 1; k < i; k++) {
      if (a[k] < a[i]) {
        f[i] = max(f[i], f[k] + 1);
      }
    }
  }
  int ans = -1;
  for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
  cout << ans << endl;
  return 0;
}

1017. 怪盗基德的滑翔翼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;

const int N = 110;
int a[N], f[N];

int main() {
  int K;
  cin >> K;
  while (K--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int res = 0;
    // 正向求解 LIS 问题
    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]);
    }

    // 逆向求解 LIS 问题
    for (int i = n; i >= 1; i--) {
      f[i] = 1;
      for (int j = n; 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;
}

1014. 登山

登山 DP 分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;

const int N = 1010;
int f[N], g[N], a[N];

int 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 = 1; j < i; j++) {
      if (a[j] < a[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 (a[j] < a[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); // a[i] 会被计算两次，这里减一
  cout << res << endl;
  return 0;
}

482. 合唱队形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;

const int N = 110;
int f[N], g[N], a[N];
int 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 = 1; j < i; j++) {
      if (a[j] < a[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 (a[j] < a[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;
}

1012. 友好城市

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 5010;
typedef pair<int, int> PII;

int f[N];
PII a[N];
int n;
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
  sort(a + 1, a + n + 1);
  int res = 0;
  for (int i = 1; i <= n; i++) {
    f[i] = 1;
    for (int j = 1; j < i; j++) {
      if (a[j].second < a[i].second) {
        f[i] = max(f[i], f[j] + 1);
      }
    }
    res = max(res, f[i]);
  }
  cout << res << endl;
  return 0;
}

1016. 最大上升子序列和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

const int N = 1010;
int f[N], a[N];
int 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;
}