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 bxsj at 2007-11-04 11:02:14 on Problem 1015
In Reply To:Re:这题递推运算量好像很可能上亿啊!递归内存不允许啊!!!咋办!!! Posted by:longinus at 2007-10-02 12:07:50
这种DP的思路对吗?
定义a[i][j][k]为前i个人中选j个人,使D-P的和等于k时D+P和的最大值
那么a[i][j][k]=max(a[i-1][j][k],a[i-1][j-1][k-Di+Pi]+Di+Pi),根据选大的结果来判断是否选用第j个人。

但你的代码的DP好像是这样的
定义a[i][j]为前n个人中选i个,使D-P的和等于k时D+P和的最大值
 a[i][j]=max{a[i-1][j-Dk+Pk]+Dk+Pk)   遍历k
这种思路对吗???它满足最优子结构?好像每个Jury只有一个人吧,选了一次就不能再选了。
举个例子,如果计算完a[i-1][j]后发现选择了第k个人,那么在计算a[i][j+Dk-Pk]的时候因第k个人已经被选择,就不存在a[i-1][j]+Dk+Pk了,但是很显然可能存在不使用第k个人也能选出i-1个人使D-P的和为j,这时候我再选择第k个人,就可以凑出选i个人(包括第k个人)且D-P的和为j了

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