汕头网站建设平台,网站域名如何实名认证,小程序致美发型设计,那种网站打不开题目链接#xff1a; https://vjudge.net/problem/UVA-12511 题目大意#xff1a; 给定两个序列#xff0c;求出两个序列的最长公共上升子序列#xff08;严格上升#xff09;。 解题过程#xff1a; 比赛的时候没有做出来#xff0c;非常咸鱼的一场比赛#xff0c;当时… 题目链接 https://vjudge.net/problem/UVA-12511 题目大意 给定两个序列求出两个序列的最长公共上升子序列严格上升。 解题过程 比赛的时候没有做出来非常咸鱼的一场比赛当时是想错了状态。当时想的状态是定义dp[i][j]意味以第一个串第前i个元素第二个串前j个元素的最长公共上升子序列长度。 但是这样定义状态有后效性比如当前我知道dp[i][j]要以这个状态进行转移的话需要他是以那个状态转移而来的换句话说我转移的时候要知道他是以前j个数中那一个结尾的。 如果换一种方式dp[i][j]代表以第一个序列前i个元素并且以第i个结束第二个序列前j个元素并且以第j个元素结尾的最长上升子序列的长度。 这样加入的限制太多不容易找出状态转移方程或者转移起来太麻烦。 题目分析 这里以dp[i][j]表示第一个序列中前i个元素第二个序列前j个元素并且以第j个元素为结尾的最长上升子序列。 这样对比前两种状态表示方式有两种好处一是无后效性dp[i][j]的第二维就确定了这个序列是以那一个元素结尾。二是容易进行转移对于dp[i][j]可由两种方式转移而来 dp[i][j]{dp[i−1][j],max(dp[i−1][k])1,a[i]≠b[i]k∈[1,j−1]∧b[k]b[j]∧a[i]b[i] 这里的k可以在循环中找出时间复杂度为O(n2). AC代码 #include bits/stdc.h
using namespace std;const int MAX 1123;int dp[MAX][MAX], a[MAX], b[MAX];int main() {int T;scanf(%d, T);while (T--) {int n, m;scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);}scanf(%d, m);for (int i 1; i m; i) {scanf(%d, b[i]);}memset(dp, 0, sizeof(dp));for (int i 1; i n; i) {int maxn 0;for (int j 1; j m; j) {//不相等时的转移dp[i][j] dp[i-1][j];//更新maxn变量表示当前小于a[i]的dp[i-1][k]的最大值if (a[i] b[j] maxn dp[i-1][j])maxn dp[i-1][j];//相等的话if (a[i] b[j])dp[i][j] maxn1;}}int ans 0;for (int i 1; i m; i) {ans max(ans, dp[n][i]);}printf(%d\n, ans);}
} 转载于:https://www.cnblogs.com/ACMFish/p/7222830.html
