问题描述 给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 参考大佬的博客
#include<stdio.h> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int dp[107][200007]; //i表示前i个数，j表示前i个数的和，dp[][]里面储存的是bi的和 int t=100000,manx=200000;//+t防止下标为负数 int inf=-100000009;//因为dp中bi的和可能为负数，所以初始化为一个很大的负数 int main() { int n; scanf("%d",&n); int ai[107],bi[107]; for(int i=1;i<=n;i++) scanf("%d%d",&ai[i],&bi[i]); //初始化 fill(dp[0],dp[0]+107*200001,inf); for(int i=1;i<=n;i++) dp[i][t+ai[i]]=bi[i]; for(int i=1;i<=n;i++) { for(int j=0;j<=manx;j++) { dp[i][j]=max(dp[i][j],dp[i-1][j]); if(j - ai[i] >= 0 ) //应为j是从0开始递推的这里是保证它的合法性 dp[i][j]=max(dp[i][j],dp[i-1][j-ai[i]]+bi[i]); } } int res=0; for(int j=t;j<=manx;j++) { if(dp[n][j]>=0)//这里少写了一个等于号，最后一组数据过不了，我淦 res=max(res,dp[n][j]+j-t); } printf("%d",res); return 0; }