问题描述

蓝桥杯算法提高 最大值问题

问题描述
　　给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

下面是我写的 只得了24分

 public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        List<String> lis1=new ArrayList<String>();
        List<String> lis2=new ArrayList<String>();
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=0;i<n;i++){
            lis1.add(sc.next());
        }
        int f=m*2;
        for(int i=0;i<f;i++){
            String s=sc.next();
            if(s.equals("ADD"))f+=1;
            lis2.add(s);
        }
        for(int i=0;i<lis2.size();i++){
            if(lis2.get(i)!=null){
            if(lis2.get(i).equals("DEL")){
                lis1.remove(lis2.get(i+1));
            }
            if(lis2.get(i).equals("ADD")){
                lis1.add(lis1.indexOf(lis2.get(i+1)),lis2.get(i+2));
            }
            }
        }
        System.out.println(lis1.size());
        for (String string : lis1) {
            System.out.print(string+" ");
        }
    }

解决方案

 #include<iostream>
using namespace std;
int a[100],b[100],n;
int res;
int dp(int x,int y,int n)
{
int ret;
if(n==0)
if(x+a[n]>=0&&y+b[n]>=0&&a[n]+b[n]>0)
ret=a[n]+b[n];
else
ret=0;
else if(a[n]+b[n]>0&&x+a[n]>=0&&y+b[n]>=0)
ret=max(dp(x,y,n-1),dp(x+a[n],y+b[n],n-1)+a[n]+b[n]);
else
ret=dp(x,y,n-1);
return ret;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i]>>b[i];
res=dp(0,0,n-1);
cout<<res;
}

解决方案二：

public >
public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int c=sc.nextInt();

int b[]=new int[c];

int array[]=new int[b.length*2];

for(int i=0;i<(array.length);i++){

    array[i]=sc.nextInt();

}

for(int i=0;i<b.length;i++){

    b[i]=array[(i+1)*2-1]+array[(i+1)*2-2];

}

Arrays.sort(b);

for (int i : b) {

    System.out.println(i);

}

if(c==1)

    if(b[b.length-1]>=0)

        System.out.println(b[b.length-1]);

        else System.out.println();

else

if(b[b.length-1]>=0&&b[b.length-2]>=0)

System.out.println(b[b.length-1]+b[b.length-2]);

else System.out.println();

}

}