滴，集训第二十天打卡。
老师又开了一个DP训练..
大多都要打印路径..真是.. 太吃鸡了！
昨天还做了百度之星的资格赛，也有一题打印路径的，
但是要等时间过了再放上来，嘻嘻。
51Nod 1006 最长公共子序列Lcs
题目大意：求不连续的最长公共子序列哦
思路：先DP得到每个位置的最长公共子序列，再回溯输出。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int s[1001][1001]; int main() { char a[1001],b[1001],c[1001]; int i,j,aa,bb,o=0,k; scanf("%s",a); scanf("%s",b); aa=strlen(a); bb=strlen(b); memset(s,0,sizeof(s)); for(i=1;i<=aa;i++) { for(j=1;j<=bb;j++) { if(a[i-1]==b[j-1]) s[i][j]=s[i-1][j-1]+1; else s[i][j]=max(s[i-1][j],s[i][j-1]); } } k=0; for(i=aa,j=bb;i>=1&&j>=1;) { if(a[i-1]==b[j-1]) { c[k++]=a[i-1]; i--; j--; } else if(s[i][j-1]>s[i-1][j]) j--; else i--; } for (i=k-1;i>=0;--i) printf("%c",c[i]); printf("\n"); }
