蓝桥杯 算法提高 求最大值

算法提高 求最大值
时间限制：1.0s 内存限制：256.0MB
提交此题
问题描述
　　给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

思路

我刚开始看，花了很长时间，的确挺难理解的。好在最后画图模拟发现其运行规则和01背包非常像，大概就是其变种，主要是要处理好负数问题。直接贴代码，代码上有注释解析：

代码

#include<iostream>
#include<algorithm> 
using namespace std;

#define INF 0x3f3f3f3f
#define t 100000 //我们将每个元素+t后存储，以100000为'0' 
#define N 200001 //每个元素之和最大不会超过20w，所以背包容量最大也就为N-1 
int dp[105][N];     //dp[i][j]代表前i个元素中，最大所有b[i]元素和的值,j为a[i]满足的容量，也就是说把a[i]当成背包容量,b[i]为价值，不过a需要加上t，避免负数 
int A[105],B[105];

int getAns(int len){

for(int i = 0;i<len;i++){   //刚开始需要对dp总每个容量的进行初始化，都为-INF,因为b[i]的累加有可能是负数，所以不能初始化为0！，必须初始化为小于-200000，因此取-INF 
for(int j = 0;j<N;j++)
            dp[i][j] = -INF;
    }

for(int i = 0;i < len;i++)
        dp[i][A[i] + t] = B[i]; //这步是必须的，dp开始前的初值设置，表示当前前i个中，b[j]和最大的值为B[i]，当然只是初试设置，可能随着程序运行改变其j所在的值 

for(int i = 1;i < len;i++){
for(int j = 0;j<=N;j++){//遍历0 - N之间所有容量，类似01背包的转移方程 
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
if(j - A[i] < 0 || j-A[i] > N-1)continue;
            dp[i][j] = max(dp[i][j],dp[i-1][j-A[i]]+B[i]);
        }
    }

int result = -INF;
for(int j = 0;j<=t;j++){ //最后需要筛选符合的，因为有负数，所以必须从大于100000的地方开始找b[j]最大和，找到符合j+dp[len-1][j+t]的最大，就是符合条件的
//如果结果没变，说明没有符合的条件，输出0 
if(dp[len-1][j+t]>=0){
            result = max(result,dp[len-1][j+t]+j);
        }
    }
return result;
}

int main(){

int n;
cin>>n;
int len = 0;
for(int i = 0;i<n;i++){
int x,y;
cin>>x>>y;
if(x < 0 && y < 0)continue;//把都是负数的值剔除，没必要参与运算 
        A[len] = x;
        B[len++] = y;
    }

int ans = getAns(len);
if(ans <= -INF)cout<<0<<endl;
else cout<<ans<<endl;
return 0;
}