骑车路线（DP）
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
Tomislav最近发现自己的身材完全走样了，她走楼梯都变得很累。一天早上她起来以后，她决定恢复姣好的身材。她最喜欢的运动是骑自行车，因此她决定在本地的小山上做一次旅行。
她骑自行车的路线可以描述为N个数字的数列，每个数字表示每一段路地海拔高度。Tomislav最感兴趣的是最长的高度一直上升的子序列，她称这一段路为爬坡，Tomislav只想考虑这段爬坡的高度差（即开始和最后的数字的差距），而不是什么路程长度。
一段爬坡路被定义为至少两个连续的上升数列。例如，我们考虑如下路线数列12 3 5 7 10 6 1 11，这里有两个爬坡，第一个爬坡（3 5 7 10）的高度差是7，第二个爬坡的高度差是10（1 11）。
帮助Tomislav计算高度差最大的爬坡的高度差。
输入输出格式
输入描述:
多组测试数据输入。 第一行是一个正整数N (1<= N <= 1000), 描述了路线数列。 第二行有N个正整数，每个正整数Pi (1<= Pi <= 1000)表示相应路段的海拔高度。
输出描述:
所有爬坡中的最大高度差，如果路线数列里面没有爬坡，就输出0。
输入输出样例
输入样例#:
复制
5 1 2 1 4 6 6 10 8 8 6 4 3
输出样例#:
复制
5 0
题目来源
华东师范大学2021年机试题
#include<bits/stdc++.h> using namespace std; int dp[1005]; int dp1[10005]; int dp2[10005]; int t[10005]; // 重量/耗时 int v[10005]; // 价值 int s[1005]; int pre[100005]; int main(){ int n, w; string str1, str2; while(cin>>n){ for(int i = 0; i < n; i ++){ cin>>s[i]; dp[i] = 0; } int m = 0;//最大长度 int start;//开始的队头 int count = 0; int temp = 0; int i = 1; bool yes = false; while(i < n){ if(s[i] > s[i - 1]){ start = i -1; while(s[i] > s[i - 1]){ i ++; temp = i - 1; } int temp1 = s[temp] - s[start]; // cout<<s[temp]<<" "<<s[start]<<endl; if(temp1 > m){ m = temp1; } count ++; } i ++; }// if(count > 1){ cout<<m<<endl; } else{ cout<<"0"<<endl; } } }最长连号
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
输入n个正整数，（1<=n<=10000),要求输出最长的连号的长度。（连号指从小到大连续自然数）
输入输出格式
输入描述:
第一行，一个数n; 第二行，n个正整数，之间用空格隔开。
输出描述:
一个数，最长连号的个数。
输入输出样例
输入样例#:
复制
10 3 5 6 2 3 4 5 6 8 9
输出样例#:
复制
5
题目来源
中山大学机试题
#include<bits/stdc++.h> using namespace std; int dp[1005]; int dp1[10005]; int dp2[10005]; int t[10005]; // 重量/耗时 int v[10005]; // 价值 int s[1005]; int pre[100005]; int main(){ int n, w; string str1, str2; while(cin>>n){ for(int i = 0; i < n; i ++){ cin>>s[i]; } int temp = 0; int m = 1, sum = 1; for(int i = 1; i < n; i ++){ if(s[i] - s[i - 1] == 1){ m ++; } else{ m = 1; } if(m > sum){ sum = m; } } cout<<sum<<endl; } }最长公共子序列LCS
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
问题描述：输入2个子串， 输出这2个子串的最大公共子串
输入：
abcd acb abc
输出：
ab
输入输出格式
输入描述:
如题
输出描述:
如题
输入输出样例
输入样例#:
复制
acb abc
输出样例#:
复制
ab
题目来源
复旦大学机试题
#include<bits/stdc++.h> using namespace std; #define N 1005 int dp[N][N] = {0}; //int s1[N] = {0}; //int s2[N] = {0}; int main(){ int n; string s1, s2; while(cin >> s1 >> s2){ int n1 = s1.size(); int n2 = s2.size(); //肌肉记忆：多组输入必须擦黑板！ memset(dp, 0, sizeof(dp)); s1 = ' ' + s1; s2 = ' ' + s2; for(int i = 1; i <= n1; i ++){ for(int j = 1; j <= n2; j ++){ if(s1[i] == s2[j]){ dp[i][j] = dp[i - 1][j - 1] + 1; } else{ dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } string result = ""; int i = n1, j = n2; while(i > 0 && j > 0){ if(s1[i] == s2[j]){ result = s1[i] + result; i --; j --; } else if(dp[i - 1][j] > dp[i][j - 1]){ i --; } else { j--; } } cout<<result<<endl; } return 0; }