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:这题递推运算量好像很可能上亿啊!递归内存不允许啊!!!咋办!!!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator