网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索

 
 
 
日一二三四五六
       
       
       
       
       
       

签到排名:今日本吧第个签到,

本吧因你更精彩,明天继续来努力!

本吧签到人数:0

一键签到
成为超级会员,使用一键签到
一键签到
本月漏签0次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行补签。
连续签到:天  累计签到:天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
07月25日漏签0天
acm吧 关注:26,576贴子:48,342
  • 看贴

  • 图片

  • 吧主推荐

  • 游戏

  • 21回复贴,共1页
<<返回acm吧
>0< 加载中...

动态规划求解

  • 只看楼主
  • 收藏

  • 回复
  • 千手猪圈
  • 大幸运星
    7
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
(动态规划)
问题描述
  给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
求个思路


  • quailty
  • 算法狂人
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
dp[i][j]表示已经考虑了前i个pair并且a[i]的和为j时b[i]的和的最大值


2025-07-25 23:30:35
广告
不感兴趣
开通SVIP免广告
  • 好地方bug
  • 霸者横拦
    9
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
就你可以dp(i,j)表示前i个中,选择了和为j的a的答案的最大值。这样你就维护出了所有需要的信息,然后每次你有两个决策,要么取,要么不取,然后转移就好了
来自Lumia830


  • 诗语千叶
  • 路人甲
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼


  • 晚安之安
  • 路人甲
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
#include <iostream>
using namespace std;
#include <memory.h>
#include <cmath>
#include<algorithm>
int a[100][2];
int sum[100][200000];
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[]) {
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i][0]>>a[i][1];
for(int j=0;j<n*2000;j++)
sum[i][j]=-0x3f3f3f3f;
}
int t=n*1000;
sum[0][0+t]=0;
sum[0][a[0][0]+t]=a[0][1];
for(int i=1;i<n;i++){
for(int j=0;j<2000*n;j++){
sum[i][j]=sum[i-1][j];
for(int k=0;k<2000*n;k++)
sum[i][a[i][0]+k]=max(sum[i][a[i][0]+k],sum[i-1][k]+a[i][1]);
}
}
int temp=-0x3f3f3f3f;
for(int j=0;j<2000*n;j++){
if(j-t>=00&&sum[n-1][j]>=0)
temp=max(sum[n-1][j]+j-t,temp);
}
cout<<temp;
return 0;
}


  • sunnyvin_深哥
  • 路人甲
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼


  • sunnyvin_深哥
  • 路人甲
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼


  • 嘿楼主_
  • 自以为是
    5
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
这题蓝桥官网的,向老师要代码院校账号可以有代码


登录百度账号

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频!
  • 贴吧页面意见反馈
  • 违规贴吧举报反馈通道
  • 贴吧违规信息处理公示
  • 21回复贴,共1页
<<返回acm吧
分享到:
©2025 Baidu贴吧协议|隐私政策|吧主制度|意见反馈|网络谣言警示