A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© LSL321` 中级黑马   /  2016-2-19 17:17  /  1120 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

问题描述

  给n个有序整数对ai bi,你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负,bi之和非负。

输入格式

  输入的第一行为n,数对的个数
  以下n行每行两个整数 ai bi

输出格式

  输出你选定的数对的ai+bi之和

样例输入

5
-403 -625
-847 901
-624 -708
-293 413
886 709

样例输出

1715

数据规模和约定

  1<=n<=100
  -1000<=ai,bi<=1000

2 个回复

倒序浏览
带条件的动态规划,貌似有点难度
给你说下我的大体思路,能不能得到精确解没有证明过,
令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的验证,通过之后再比较大小,最后得到结果。
回复 使用道具 举报
本帖最后由 oassuperhan 于 2016-2-19 21:06 编辑

补充:另外一个要注意的是初始值,也就是J1=s1,   S1=max{s1,0},上面的Ji的方程有错误,难怪感觉有点不对,Ji=max{(Ji-1 + si), (Si-1 + si), (Ji-1),(Si-1)},里面的数字不进行Ai和Bi的判断,你试下这样行不行。

一个问题只要得出问题的状态转移方程,就能得到底部向上的动态规划算法,我好多年没有研究算法题目,忘得差不多了,上面的状态转移方程好像有点问题,没有证明过是不是准确,但是大体思路是这样子,你再修改下就OK了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马