蓝桥杯 算法提高 求最大值

时间:2022-09-09 21:25:14
题意:
给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
思路:
不直接计算选定的数的ai+bi的和,而是转化为计算在ai的和一定的情况下尽量使选定的bi的和最大。于是变成为一个和01背包差不多的问题。首先过滤掉所有ai和bi均小于0的数对,令dp[i][j]表示前i个数对,选定的ai的和为j的情况下bi的和的最大值,将dp[i][j]初始化为-INF,再将所有已知合法情况初始化:dp[i][a[i]] = b[i],之后dp[i][j] = max(dp[i - 1][j], dp[i][j]),若j - a[i]存在,dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + b[i])。为避免负数作为数组下标,要加一个偏移量。
实现:
 1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5
6 const int INF = 0x3f3f3f3f;
7 const int t = 100000;
8 int a[105], b[105], dp[105][200005], n, p, q;
9 int solve(int n)
10 {
11 for (int i = 0; i < n; i++)
12 {
13 for (int j = -t; j <= t; j++)
14 {
15 dp[i][j + t] = -INF;
16 }
17 }
18 for (int i = 0; i < n; i++)
19 dp[i][a[i] + t] = b[i];
20 for (int i = 1; i < n; i++)
21 {
22 for (int j = -t; j <= t; j++)
23 {
24 dp[i][j + t] = max(dp[i - 1][j + t], dp[i][j + t]);
25 if (j + t - a[i] < 0 || j + t - a[i] > 200000)
26 continue;
27 dp[i][j + t] = max(dp[i][j + t], dp[i - 1][j + t - a[i]] + b[i]);
28 }
29 }
30 int ans = -INF;
31 for (int j = 0; j <= t; j++)
32 {
33 ans = max(ans, dp[n - 1][j + t] >= 0 ? j + dp[n - 1][j + t] : -INF);
34 }
35 return ans;
36 }
37
38 int main()
39 {
40 cin >> n;
41 int cnt = 0;
42 for (int i = 0; i < n; i++)
43 {
44 cin >> p >> q;
45 if (p < 0 && q < 0)
46 continue;
47 a[cnt] = p;
48 b[cnt++] = q;
49 }
50 int ans = solve(cnt);
51 if (ans <= -INF)
52 cout << "0" << endl;
53 else
54 cout << ans << endl;
55 return 0;
56 }