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

我也是这样做的 不过数组开 int dp[5001][5001] 的话 超内存,用 short 水过了

Posted by acmer1183 at 2010-04-13 21:51:25 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