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大学生程序设计竞赛训练》暑期课面向全球招生!

简单区间DP

Posted by hzoi2017_zyc at 2018-05-12 18:30:14 on Problem 3056
正常区间DP 答案无误
两端相等 域值加一
转移方程:
for(int l=1;l<p;l++){//l为左右端点的差值 
	for(int i=1;i+l<=p;i++){
		int j=i+l;//i,j为左右端点 
		if(a[i]==a[j])
			dp[i][j]=dp[i+1][j-1]+1;
		else 
			dp[i][j]=dp[i+1][j-1];
		for(int k=i;k<j;k++)//k为区间断点 
			dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
	}
}
但是效率堪忧 TLE 凉凉
仔细读题我们会发现,题目中给了 p一定为偶数 即所有有效区间长度均为偶数
我们可以得到如下优化转移:
for(int l=1;l<p;l+=2){
	//l为左右端点的差值,j-i+1为偶数,即j-i为奇数,从1开始,每次加2 
	for(int i=1;i+l<=p;i++){
		int j=i+l;//i,j为左右端点 
		if(a[i]==a[j])
			dp[i][j]=dp[i+1][j-1]+1;
		else 
			dp[i][j]=dp[i+1][j-1];
		for(int k=i+1;k<j;k+=2)
			//k为区间断点,同上,从dp[i][i+1]开始,每次长度加2 
			dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
	}
}
2000ms左右,可过

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