# Chapter 1 of AcWing algorithm improvement course - dynamic programming - longest ascending subsequence model

## 1017. Strange thief Kidd's glider wing

Input example:

```3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10```

Output example:

```6
6
9```

Solution:

After determining the glide direction, it is transformed into LIS problem, which is equivalent to finding the longest descent subsequence in the forward and reverse directions respectively, and taking the maximum value

AC Code:

```#include<iostream>
using namespace std;
#include<cstring>

const int N = 110;

int a[N];
int f1[N], f2[N];
int t, n;

int main() {
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
f1[i] = f2[i] = 1;
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] < a[i])   f1[j] = max(f1[j], f1[i] + 1);
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] > a[i])   f2[j] = max(f2[j], f2[i] + 1);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, max(f1[i], f2[i]));
}
cout << ans << endl;
}
}```

## 1014. Mountaineering

Input example:

```8
186 186 150 200 160 130 197 220```

Output example:

`4`

Solution:

The route of this problem requires an A-shape. We first find the longest ascending subsequence f1 [], and then find the longest ascending subsequence f2 []; Then traverse from beginning to end and take the maximum value of f1[i]+f2[i]-1

AC Code:

```#include<iostream>
#include<cstring>
using namespace std;

int a[1010];
int n;
int b[1010];
int f1[1010], f2[1010];

int main() {
cin >> n;
int k = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
f1[i] = 1;
f2[i] = 1;
if (a[i] == a[i - 1])    continue;//duplicate removal
b[k++] = a[i];
}
k--;
for (int i = 1; i < k; i++) {
for (int j = i + 1; j <= k; j++) {
if (a[j] > a[i])   f1[j] = max(f1[j], f1[i] + 1);//Forward finding the longest ascending subsequence
}
}
for (int i = n; i > 1; i--) {
for (int j = i - 1; j >= 1; j--) {
if (a[j] > a[i])   f2[j] = max(f2[j], f2[i] + 1);//Reverse the longest ascending subsequence
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, f1[i] + f2[i] - 1);
}
cout << ans << endl;
}```

## 482. Chorus formation

Input example:

```8
186 186 150 200 160 130 197 220```

Output example:

`4`

Solution:

It's as like as two peas, but only n-ans.

AC Code:

```#include<iostream>
#include<cstring>
using namespace std;

int a[1010];
int n;
int b[1010];
int f1[1010], f2[1010];

int main() {
cin >> n;
int k = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
f1[i] = 1;
f2[i] = 1;
if (a[i] == a[i - 1])    continue;//duplicate removal
b[k++] = a[i];
}
k--;
for (int i = 1; i < k; i++) {
for (int j = i + 1; j <= k; j++) {
if (a[j] > a[i])   f1[j] = max(f1[j], f1[i] + 1);//Forward finding the longest ascending subsequence
}
}
for (int i = n; i > 1; i--) {
for (int j = i - 1; j >= 1; j--) {
if (a[j] > a[i])   f2[j] = max(f2[j], f2[i] + 1);//Reverse the longest ascending subsequence
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, f1[i] + f2[i] - 1);
}
cout << n - ans << endl;
}```

## 1012. Sister Cities

Input example:

```7
22 4
2 6
10 3
15 12
9 8
17 17
4 2```

Output example:

`4`

Solution:

By sorting the city coordinates on one side from small to large, we can find that the way to make the routes not staggered is to find the longest ascending subsequence of the city coordinates on the other side. Then it was converted into a LIS naked question.

Because the data in this question is relatively small, O(n^2) is OK

AC Code:

```#include<iostream>
using namespace std;
#include<cmath>
#include<algorithm>
int n;
pair<int, int> p[5050];

int f[5050];

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

```

## 1016. Maximum ascending subsequence and

Input example:

```7
1 7 3 5 9 4 8```

Output example:

`18`

Solution:

The train of thought is no different from the previous questions

AC Code:

```#include<iostream>
using namespace std;

int a[1010];
int f[1010];
int n;

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
f[i] = a[i];
}
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] > a[i])   f[j] = max(f[j], f[i] + a[j]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, f[i]);
}
cout << ans << endl;
}```

## 1010. Interceptor missiles

Input example:

`389 207 155 300 299 170 158 65`

Output example:

```6
2```

Solution:

Greed + DP

First question: the length of the longest Non rising subsequence will not be repeated.

The second question: the number of least Non rising subsequences that can cover the whole sequence

For the second question:

Solution 1: there is a conclusion that I don't prove here (it's a little complicated. I'm afraid to talk about the wrong Guide).

Assuming that the whole series can be divided into at least n Non rising subsequences (the answer to this question), the sequence composed of the number at the end of each Non rising subsequence must be a rising subsequence

Conclusion: the number of least non ascending subsequences that can cover the whole sequence = = the longest ascending subsequence

Solution 2: we store the ending number of each existing Non rising subsequence in an array G []. When dealing with each subsequent number x, we go to G [], See if there is a number larger (or equal to) than this number (if so, set this number as y); if so, it means that the existing subsequence does not rise even if this number is added to the subsequence, so we update the y value to X, (Note: only update once, that is, only update one number, that is, y; here y is the number larger than x but closest to x, which is the optimal solution, and readers can think about why); if not, it means that we need to reopen a system, that is, reopen a subsequence. At present, this subsequence has only one number, and the end is also its own Already, we save it in the array g[].

AC code 1:

```#include<iostream>
using namespace std;

int a[1010];
int f[1010];
int g[1010];
int n = 1;
int main() {
while (cin >> a[n])    f[n] = 1, n++;
n--;
int ans = 0;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] <= a[i])   f[j] = max(f[j], f[i] + 1);
ans = max(ans, f[j]);
}
}
cout << ans << endl;
ans = 0;
for (int i = 1; i <= n; i++) {
f[i] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] > a[i])   f[j] = max(f[j], f[i] + 1);
ans = max(ans, f[j]);
}
}
cout << ans << endl;
}
```

AC code 2:

```#include<iostream>
using namespace std;

int a[1010];
int f[1010];
int g[1010];
int n = 1;
int main() {
while (cin >> a[n])    f[n] = 1, n++;
n--;
int ans = 0;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] <= a[i])   f[j] = max(f[j], f[i] + 1);
ans = max(ans, f[j]);
}
}
cout << ans << endl;
int cnt = 0;
for (int i = 1; i <= n; i++) {
int k = 0;
while (k <= cnt && g[k] < a[i]) k++;//Note: here is g [k] < a [i]
if (k > cnt)   cnt++;
g[k] = a[i];
}
cout << cnt << endl;
}
```

## 187. Missile defence systems

Input example:

```5
3 5 2 4 1
0 ```

Output example:

`2`

Example explanation:

For the given example, a minimum of two defense systems are required.

One set of missiles with a shooting height of 3,43,4 and the other with a shooting height of 5,2,15,2,1.

Solution:

DFS, iteration deepening, pruning, greed

The meaning of this question is almost the same as that of the previous question, but it is no longer that the monotonicity of each subsequence is the same; The monotonicity of each subsequence is not related to each other.

Then we need to search to see which sequence the current number should be placed at the end or a single sequence

AC Code:

```#include<iostream>
using namespace std;
int n;
int a[55];
int ans = 0;
int up[55], down[55];
void dfs(int ps, int us, int ds) {
if (ds + us >= ans)   return;
if (ps == n) {
ans = us + ds;
return;
}
int k = 0;
//rise
while (k < us && up[k] >= a[ps])  k++;
int t = up[k];
up[k] = a[ps];
if (k >= us)   dfs(ps + 1, us + 1, ds);
else    dfs(ps + 1, us, ds);
up[k] = t;//Restore site
//decline
k = 0;
while (k < ds && down[k] <= a[ps])    k++;
t = down[k];
down[k] = a[ps];
if (k >= ds)   dfs(ps + 1, us, ds + 1);
else    dfs(ps + 1, us, ds);
down[k] = t;//Restore site
}
int main() {
while (cin >> n && n) {
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ans = n;
dfs(1, 0, 0);
cout << ans << endl;
}
}
```

## 272. Longest common ascending subsequence

Input example:

```4
2 2 1 3
2 1 2 3```

Output example:

`2`

Solution:

We require not only ascending subsequences, but also public ones. Isn't it disgusting, but it's still relatively simple

Let's first look at the status representation:

f[i][j]: represents the set of common ascending subsequences ending in b[j] in all a[1 ~i] and b[1 ~j]
The value of f[i][j] is equal to the maximum length in the subsequence of the set

Suppose we are currently dealing with a[i] and b[j]:

State transition:

Firstly, the set represented by f[i][j] is divided into two non redundant subsets according to whether the common subsequence contains a[i]:

1: Subset without a[i], Max f[i - 1][j]

2: The subset containing a[i] is further divided according to the number of the penultimate element of the subsequence in b []:
The subsequence contains only b[j] a number with a length of 1;
The penultimate number of subsequences is the set of b[1], and the maximum length is f[i - 1][1] + 1;
...
The penultimate number of subsequences is the set of b[j - 1], and the maximum length is f[i - 1][j - 1] + 1;

If it is realized directly according to the above ideas, a triple cycle is required:

```for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) {
int maxl = 1;
for (int k = 1; k < j; k++) {
if (b[j] > b[k]) {
maxl = max(maxl, f[i - 1][k] + 1);
}
//if (a[i] > b[k]) {
//    maxl = max(maxl, f[i - 1][k] + 1);
//}
}
f[i][j] = max(f[i][j], maxl);
}
}
}```

But the triple loop obviously doesn't work. The time complexity is O(n^3), which will TLE

Find ways to reduce time complexity

We find that maxl is the maximum prefix of f[i-1][k] satisfying B [J] > b [k], that is, a [i] > b [k] (because b[j]==a[i]). We refer maxl to the first layer of loop, so there are only two layers of loop

```for (int i = 1; i <= n; i++) {
int maxl = 1;
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j])	f[i][j] = max(f[i][j], maxl);
if (a[i] > b[j])	maxl = max(maxl, f[i - 1][j] + 1);
}
}```

AC Code:

```#include<iostream>
using namespace std;
#include<cstring>
#include<cmath>
#include<algorithm>
int a[3010],b[3010];
int f[3010][3010];
int n;

int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
int maxl=1;
for (int i = 1; i <= n; i++) {
int maxl = 1;
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j])	f[i][j] = max(f[i][j], maxl);
if (a[i] > b[j])	maxl = max(maxl, f[i - 1][j] + 1);
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,f[n][i]);
}
cout<<ans<<endl;
}```

Keywords: Algorithm AcWing

Added by demonicfoetus on Mon, 27 Dec 2021 02:52:22 +0200