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:第一个DP啦...说下思路哈...跟Discuss讨论的不太一样啦(简单点),牛人可以忽略啦..

Posted by Desertangle at 2010-05-20 10:19:35 on Problem 3671
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:
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