问题描述
给n个有序整数对ai bi,你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负,bi之和非负。
输入格式
输入的第一行为n,数对的个数
以下n行每行两个整数 ai bi
以下n行每行两个整数 ai bi
输出格式
输出你选定的数对的ai+bi之和
样例输入
5
-403 -625
-847 901
-624 -708
-293 413
886 709
-403 -625
-847 901
-624 -708
-293 413
886 709
样例输出
1715
数据规模和约定
1<=n<=100
-1000<=ai,bi<=1000
-1000<=ai,bi<=1000
思路:
讲道理好嘛~~自己做出来的dp耶~~~虽然用了大概两个点写出来的~~~~23333......好开心
额....1次提交给了50分,发现dp[][]数组初始化的时候生生二维范围生生多了10倍....蓝桥杯好坑好友善...居然不是0分....
2次提交给了75分,明明无比的正确好嘛.....突然想到ai和>=0 bi和>=0 那么最后的ans 肯定是>=0啊....那我为什么要初始化成-inf啊....手一抖改过来了。但是吧,这有什么关系呢~~~但是这就是100分了~~~啊啊啊....好坑。
突然间明白为什么了。我是可以选0对的是吗。
比如说:
1
-2 -3
原先的ans会是-inf,正解就是0了呢。这样说,好像是我傻逼了~~~~
感觉很暴力的一个dp,跟前边做过的几个还是有相似之处的,比如说第i对一定选取的情况下!
王sir曾说这个一维就可以了,dp[i]=j,i是所有的ai和,j是所有的bi和,然后我还以为是正解,想了想我是一定要i的,因为ai是有可能重复的啊!哼。
附right代码:
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define inf 1000000000 struct Node { int a, b; }node[210]; int dp[210][200010]; //dp[i][j] = sum 表示的是 考虑前i对数 第i对数被选中时 所有的ai和为j时 所有的bi和为sum。 // dp[i][j] = max(dp[i][j], dp[k][sumb]+node[i].b); (0<=k<=i-1); int main() { int n; while(cin >> n) { int suma = 0; for (int i=0; i<n; ++i) { cin >> node[i].a >> node[i].b; suma = max(suma, suma+node[i].a); } suma +=100000; for (int i=0; i<n; ++i) { for (int j=0; j<200010; ++j) { dp[i][j] = -inf; } } dp[0][100000+node[0].a] = node[0].b; int ans = 0; // 讲道理啊,如果ans初始值是-inf,就是75分,如果是0就是100分了。 if (node[0].a >= 0 && node[0].b >= 0) ans = max(ans, node[0].a+node[0].b); for (int i=1; i<n; ++i) { dp[i][node[i].a+100000] = node[i].b; for (int j=0; j<i; ++j) { for (int k=0; k<=suma; ++k) { if (dp[j][k] != -inf) { if (k + node[i].a < 0) continue; dp[i][k+node[i].a] = max(dp[i][k+node[i].a], dp[j][k]+node[i].b); if (k+node[i].a >= 100000 && dp[i][k+node[i].a] >= 0) { ans = max(ans, k+node[i].a-100000+dp[i][k+node[i].a]); } } } } } cout << ans << endl; } return 0; }