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 wolf711988 at 2008-12-08 21:36:20 on Problem 1260
In Reply To:方程如何推?谢谢 Posted by:bakey at 2005-08-20 20:43:58
/*
决策:买,不买
f[i][0]:第i种不买的情况下买前i种要用的最少钱
f[i][1]:第i种买的情况下买前i种要用的最少钱
f[i][2]:买前i种要用的最少钱

状态转移方程:
f[i][0] = min{f[k][1]+(a[k+1]+a[k+2]+..a[i])*p[k];}(1<=k<i) //把后面的都归到第k种买
f[i][1] = f[i-1][2]+(a[i]+10)*p[i];
f[i][2] = min{f[i][0], f[i][1]}

边界条件:
p[1]存最大的,所以第一种是必买的
f[1][0] = INFI
f[1][1] = (a[1]+10)*p[1]
f[1][2] = f[1][1];

wolf711988	1260	Accepted	396K	0MS	G++	1752B	2008-12-08 21:29:44
一次AC,兴奋。。。
又一道自己想出来的DP。。。。
*/

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