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;
}