大家好,又见面了,我是全栈君。
以下代码中有打印路径。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <cmath> #include <stack> #include <map> #include <ctime> #include <iomanip> #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-6) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 1000000007 using namespace std; int A[510],B[510]; int py[510][510],px[510][510],dp[510][510] = {0}; void Output(int x,int y) { if(x == -1 && y == -1) return ; Output(px[x][y],py[x][y]); if(A[x] == B[y]) printf("%d ",A[x]); } int main() { int n,m,i,j,mlen,x,y; scanf("%d",&n); for(i = 1;i <= n; ++i) scanf("%d",&A[i]); scanf("%d",&m); for(i = 1;i <= m; ++i) scanf("%d",&B[i]); int Max = 0,ax,ay; for(i = 1;i <= n; ++i) { mlen = 0,x = -1,y = -1; for(j = 1;j <= m; ++j) { dp[i][j] = dp[i-1][j]; px[i][j] = i-1,py[i][j] = j; if(B[j] < A[i] && dp[i-1][j] > mlen) mlen = dp[i-1][j],x = i-1,y = j; if(B[j] == A[i]) dp[i][j] = mlen + 1,px[i][j] = x,py[i][j] = y; if(dp[i][j] > Max) Max = dp[i][j],ax = i,ay = j; } } if(Max) printf("%d\n",Max),Output(ax,ay); else printf("0\n"); return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115817.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...