国产探花免费观看_亚洲丰满少妇自慰呻吟_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] ); }}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 乳源| 沧源| 海盐县| 财经| 邳州市| 宝兴县| 门源| 东丽区| 环江| 正镶白旗| 凌云县| 平谷区| 五莲县| 湘潭县| 安图县| 读书| 隆子县| 潮安县| 息烽县| 华亭县| 额敏县| 保山市| 友谊县| 乌鲁木齐县| 安徽省| 措美县| 永仁县| 获嘉县| 新闻| 奈曼旗| 烟台市| 渝中区| 太仓市| 锡林郭勒盟| 青川县| 吉首市| 射阳县| 和硕县| 佳木斯市| 英山县| 永济市|