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

Re:此题为最基本的动态规划。思路如下。

Posted by djp_1 at 2007-10-20 14:57:18 on Problem 1159
In Reply To:此题为最基本的动态规划。思路如下。 Posted by:lnmm at 2007-09-04 01:47:20
看后发现自己的动规规划错了。。谢。。

> 
> 动态规划求解。
> 
> 设ch[1]..ch[n]表示字符串1至n位,i为左游标,j为右游标 ,则i从n递减,j从i开始递增。
> min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n].
> 则
> if(ch[i]==ch[j])                                    //如果两个游标所指字符相同,向中间缩小范围
>     min[i][j]=min[i+1][j-1];
> else
>      min[i][j] = 1 +  (min[i+1][j]和min[i][j-1]中的较小值);     //如果不同,典型的状态转换方程
> 
> 
> 代码就不用写了吧?很明白了 呵呵~
> 用此方法AC的同志留下言。不明白的问我。(最好是Email,时效性)

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