Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

解题报告

Posted by hzoi2017_zyc at 2018-05-13 17:16:21 on Problem 1934
O(n^2)LCS+dfs
题目大意:
	两个字符串,字典升序输出LCS的所有情况
思路:
	对于两个固定的字符串来说,LCS的大小随当前处理的长度不下降增加
	从状态转移方程可以看出,dp[i][j]不小于dp[i-1][j],dp[i][j-1]和dp[i-1][j-1],
	因此我们可以根据这条单调性对已处理好的LCS进行操作,(显然,LCS是少不了的) O(mn)++;
	Alice[i][j]/Bob[i][j] 记录两个字符串中26个英文字母对应长度中最后出现的位置
	由上述可知,对于相同的字母,下标越靠后 
	再用dfs去枚举所有情况,最后排序输出(也可以一开始就按字典序去搜字母,省去排序的步骤) 
	(感觉除了LCS,并不算DP)~
简要实现:
	 LCS略
	 for(int i=1;i<=la;i++){
	 	for(int j=1;j<=26;j++){
	 		ail[i][j]=ail[i-1][j];
		 }
		 ail[i][a[i]-96]=i;
	 } 
	 Bob同理
	 
	void dfs(int al,int bl,int l){//a中处理位置,b中处理位置,匹配长度 
		if(l==dp[la][lb]){
	 		strcpy(ans[sum++],p);//匹配成功,记录结果 
			 return ; 
		}
	 	if(dp[al][bl]+l<dp[la][lb])return ;//不符合LCS 
	 	if(al<0||bl<0)return ;//边界
		for(int i=1;i<=26;i++) {
			if(ail[al][i]>0&&bob[bl][i]>0) //存在同一个公共字母 
				dfs(ail[al][i]-1,bob[bl][i]-1,l+1);//从公共字母的前一个继续搜索 
		} 
	}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator