 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:DP嘛,水题一道!In Reply To:DP嘛,水题一道! Posted by:fangyixiang at 2008-09-04 16:33:13 略做一点补充:对于这样一个0,1序列,a1,a2,a3,...a(i-2),a(i-1),a(i)... 设f(i)为输入的数对应的结果 用DP做的话,假设f(i-2),f(i-1)已经知道了,那么求f(i)应该如下: 当取a(i)=0,那么结果肯定和f(i-1)是一样的,因为在后面追加的是0,肯定不会导致存在相邻; 当取a(i)=1,那么此时只要知道a(i-2)就可以了,因为我们可以使a(i-1)为0,这样就不会导致相邻的1了; 所以a[i]=a[i-1]+a[i-2]; Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
