算法提高 求最大值

时间:2022-09-09 21:25:02
  问题描述  给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分,,不好意思拿出来,希望会做的大神们评论或者私信我哦,小编先拜谢了