812字节跳动研发岗第三题题解
思路：动态规划
记X(A), X(B)分别为玩家A,B的个人得分，sumx为所有卡片的个人得分之和，sumy为所有卡片的团体得分之和。
f[i][j]表示 考虑 第0张~第i张 卡片的情况下，玩家A与玩家B的个人得分之差为j + sumx（即X(A) - X(B) = j + sumx）时，能得到的最大团体分。那么
记N为卡片总张数，则 f[N - 1][0] 即为所求。
显然，f为一个 N * (sum * 2 + 1)维的数组。
由于卡片张数N，最大有100，每一张卡片的个人得分x[i]最大能达到1000，所以 sum可以达到10W，数组f的空间最大可达 100 * 10W * 2 = 2000W 个元素，有超过空间限制的危险，注意到只需保留f[i - 1]，即可求出f[i]，因此采用滚动数组。
为处理方便，特别地，记f[-1]为玩家A,B均为拿取任何卡片的情况，显然，仅有f[-1][sum] = 0，f[-1][0] ~ f[-1][sum - 1] 以及 f[-1][sum + 1] ~ f[-1][2 * sum] 均为不合法的状态 (A，B分差为0时取得的团体分只有可能为0）。
将这些不合法的状态初始化为一个小于团体得分之和小于 -sumy 的值，以保证后序步骤中，从这些不合法状态得来的结果均小于0，已达到排除不合法状态的目的。
参考代码：
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <numeric>
using namespace std;
int main()
{
int N;
while (cin >> N)
{
//读入数据
vector<int> x(N), y(N);
for (int i = 0; i < N; ++i)
cin >> x[i] >> y[i];
int sumx = accumulate(x.begin(), x.end(), 0);
int sumy = accumulate(y.begin(), y.end(), 0);
//小于sumy的值，用于赋给不合法的状态
int INF = -sumy * 4;
//滚动数组f[i][j], 并将所有值初始化为INF
vector<vector<int>> f(2, vector<int>(2 * sumx + 1, INF));
int pre = 0, cur = 1;
//此时cur代表-1，将f[-1][0]赋为0
f[cur][sumx] = 0;
for (int i = 0; i < x.size(); ++i)
{
swap(pre, cur);
//此时cur代表i，pre代表i - 1, f[pre]为上一轮已求解完的状态，f[cur]为接下来要求解的状态
for (int j = 0; j < f[cur].size(); ++j)
f[cur][j] = f[pre][j]; // f[i][j] = f[i - 1][j]
for (int j = 0; j < f[0].size(); ++j)
{
if (j + x[i] < f[0].size())) f[cur][j] = max(f[cur][j], f[pre][j + x[i]] + y[i]); //f[i][j] = max(f[i][j], f[i - 1][j + x[i]] + y[i]
if (j - x[i] >= 0) f[cur][j] = max(f[cur][j], f[pre][j - x[i]] + y[i]);//f[i][j] = max(f[i][j], f[i - 1][j - x[i]] + y[i]
}
}
cout << f[cur][sumx] << endl;
}
}
腾讯成长空间 1182人发布