使用Java语言完成代码 给n个有序整数对ai bi

Question

问题描述
　　给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
使用Java语言完成代码。

Answer 1

翻译别人的C语言

import java.util.Scanner;

public class Main {
    public static int [] arrLeft = null;
    public static int [] arrRight = null;
    public static int [][] dp = new int[101][200001];//[i][j]i:第几次\\\j 消耗  dp价值
    public static void main(String[] args) {
         Scanner in = new Scanner(System.in);
         int n = in.nextInt();
         arrLeft = new int[n];
         arrRight = new int[n];
         for(int i=0;i<n;i++){
             arrLeft[i] = in.nextInt();//ai
             arrRight[i] = in.nextInt();//bi输入值
         }
         for(int i=0;i<dp.length;i++){
             for(int j=0;j<dp[0].length;j++){
                 dp[i][j] = -999999;//初始化
             }
         }
         int t = 100000;// -100000<=t<=100000//两边同时加100000重新规定0

        /**
         * 1<=n<=100
         * 　　-1000<=ai,bi<=1000
         */
        for(int i=0;i<n;i++){
             dp[i][t+arrLeft[i]] = arrRight[i];//初始化
         }

         for(int i=1;i<n;i++){
             for(int j=0;j<dp[0].length;j++){
                 dp[i][j] = Math.max(dp[i][j],dp[i-1][j]);//看看对应上一个的大小
                 if(j-arrLeft[i]<0||j-arrLeft[i]>200000)
                     continue;
                 dp[i][j] = Math.max(arrRight[i]+dp[i-1][j-arrLeft[i]],dp[i][j]);
             }
         }
         int ans = -999999;
         for(int i=0;i<=t;i++){
             if(dp[n-1][i+t]>=0)
             ans = Math.max(ans,dp[n-1][i+t]+i);
         }
         if(ans==-999999)
             System.out.println(0);
         else
        System.out.println(ans);
    }
}