问题描述 给n个有序整数对aibi,你需要选择一些整数对 使得所有你选定的数的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
#include <iostream>
#include <stdio.h>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <string>
#include<iostream>
#include<algorithm>
#include<cstring>
#include <cstdio>
using namespace std;
int d[400005];
int a[400005],b[400005];
int ss=100000;
int main() { int n; while(cin>>n) { memset(d,-1,sizeof(d)); int x,y; int s; d[200000]=1; for(inti=0;i { cin>>x>>y; if(x+y>0) for(int j=400000;j>=0;j--) { if(j-x-y>=0&&j-x-y<=400000) { if(d[j]==1&&d[j-x-y]==1) { a[j]=max(a[j],a[j-x-y]+x); b[j]=max(b[j],b[j-x-y]+y); } else if(d[j] { a[j]=a[j-x-y]+x; b[j]=b[j-x-y]+y; } d[j]=max(d[j],d[j-x-y]); if(d[j]==1) { // cout<<j<<' '<<x<<''<<y<<' '<<j-x-y<<' '<<a[j]<<''<<b[j]<<endl; } } } } else { for(int j=0;j<=400000;j++) { if(j-x-y>=0&&j-x-y<=400000) { if(d[j]==1&&d[j-x-y]==1) { a[j]=max(a[j],a[j-x-y]+x); b[j]=max(b[j],b[j-x-y]+y); } else if(d[j] { a[j]=a[j-x-y]+x; b[j]=b[j-x-y]+y; } d[j]=max(d[j],d[j-x-y]); if(d[j]==1) { //cout<<j<<' '<<x<<''<<y<<' '<<j-x-y<<' '<<a[j]<<''<<b[j]<<endl; } } } } } int i; for(i=400000;i>200000;i--) { if(d[i]==1&&a[i]>=0&&b[i]>=0) { cout<<i-200000<<endl; break; } } if(i<=200000) { cout<<"0"<<endl; } } }
此题使用c++实现的,小编写的java只得到了42分,,不好意思拿出来,希望会做的大神们评论或者私信我哦,小编先拜谢了