带条件的动态规划,貌似有点难度
给你说下我的大体思路,能不能得到精确解没有证明过,
令Ai=ai的和,Bi=bi的和,si=ai+bi,Si=si的和。
首先将列表中ai和bi同时为负的数字全部剔除。剩下的问题就是如何把问题分解。可以先不考虑题目中Ai>=0,Bi>=0的条件,很容易得到一个最大值的关系式,假设这样子得到的和称为Ji(区别于Si),那么Ji=max{(Ji-1 + si),Ji-1},如果ai+bi》0,那么Ji = (Ji-1 + si),否则就是Ji-1。需要注意,由于ai,bi可能为负数,得到的结果可能使Ai,Bi<0,那么同样再进行一个精确解的计算Si(满足Ai,Bi大于0的解),怎么获得呢?假如已知Si-1,对于xi,yi,
可以把Si表示为max={(Si-1 + si), (Ji-1+si) , Ji-1 , Si-1}大括号里的值首先进行Ai>=0&&Bi>=0的验证,通过之后再比较大小,最后得到结果。 |