国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

poj 1458 最長公共子序列

2019-11-11 05:14:08
字體:
來源:轉載
供稿:網友

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, …, xm > another sequence Z = < z1, z2, …, zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, …, ik > of indices of X such that for all j = 1,2,…,k, x ij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the PRoblem is to find the length of the maximum-length common subsequence of X and Y. Input The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. Output For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0

求最長公共子序列 狀態轉移方程 dp[i][j] 是在i的當前字符,和j的當前字符相對于前面 1~i-1 1~j-1里面最長的公共子序列。 因為題目要求的公共子序列的兩個條件是 在s里面是有次序的,在s2里面也是有次序,過了的不能再被選擇,只能不斷往后選。相當于兩個上升序列合并,但是選擇條件改變了。而那些不相同的 保持的是上一個相同的最大值。 遇到兩個相同的值,dp[i][j] 由s的上一個字符階段 i-1 里面選擇 j在1~j-1字符里面的最長公共序列里面選擇最長的dp,由于j-1是j在 1到j-1里面最長的 所以 dp[i-1][j-1]是上一個相同字符里面最長的。 為什么j-1 是1~j-1里面最長的 因為 dp[i][j] =max(dp[i-1][j],dp[i-1][j-1]),從而得到無論是i的上一階段還是當前階段i也是最長的,而且 與(1~j-1)也是最長的那個。 if(s[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]);}

#include <cstdio>#include <iostream>#include <cstring>using namespace std;int dp[1001][1001];char s[1001];char s1[1001];//if(s[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;//dp[i][j]=max(dp[i-1][j],dp[i][j-1]);int main(){ while(scanf("%s %s",s+1,s1+1)!=EOF) { memset(dp,0,sizeof(dp)); dp[0][0]=0; int len1=strlen(s+1); int len2=strlen(s1+1); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(s[i]==s1[j]) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } printf("%d/n",dp[len1][len2] ); }}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 文登市| 新郑市| 革吉县| 徐水县| 临朐县| 阜南县| 卢龙县| 乌什县| 英山县| 彭阳县| 土默特右旗| 昌宁县| 商南县| 隆子县| 苏尼特左旗| 三亚市| 应城市| 宿松县| 长汀县| 嘉义市| 韶关市| 博兴县| 巨鹿县| 昌宁县| 永清县| 阿拉善左旗| 聊城市| 那坡县| 奉贤区| 丰顺县| 华宁县| 尼勒克县| 松江区| 上蔡县| 永仁县| 噶尔县| 嘉义市| 交口县| 涞源县| 铜山县| 洮南市|