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啦...说下思路哈...跟Discuss讨论的不太一样啦(简单点),牛人可以忽略啦..In Reply To:第一个DP啦...说下思路哈...跟Discuss讨论的不太一样啦(简单点),牛人可以忽略啦.. Posted by:Desertangle at 2010-05-20 10:18:26 > 从后往前(从前到后也一样)... > a[k]为以第k条牛为转折点(也就是号码2啦)需要的次数。。 > 那么a[k +1],a[k +2]。。。a[n](a[n]为第n个开始转折需要的次数,也就是全“1”需要的次数了) > 是已知的。。 > > a[k]有两种情况: > 1、 cow[k]== 1 > 那么 a[k] = a[k +1] + 1; > 因为cow[k]是1,在计算a[k +1]时,需要cow[k]为1,不需要其改变; > 而计算a[k]时,需要cow[k]为2,需要其改变; > 2、 cow[k]== 2 > 那么 a[k] = a[k +1] - 1; > 因为cow[k]是2,在计算a[k +1]时,需要cow[k]为1,需要其改变; > 而计算a[k ]时,需要cow[k]为2,不需要其改变; 补充一下,因为如上的分析,所以a[k] 只与 a[k +1]和cow[k]有关,所以只需要记录下cow[k]就好啦。。。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator