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

## 简单区间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]);
}
}

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:

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