题解

对于 $10\%$

直接 $2^{2n}$ 枚举每天选的东西，然后求答案即可。

对于 $40\%$

考虑设 $f_{i, j}$ 表示前 $i$ 天，语文选了 $j$ 次此时的最大价值。

然后转移就是 $f_{i, j} = \max(f_{i - 1, j - 1} + a_i, f_{i - 1, j} + b_i)$。

答案就是 $f_{2n,n}$。

时间复杂度 $O(n^2)$。

对于 $100\%$

考虑一个贪心：

先全选语文，然后拿出一些换成数学。

那么每个换成数学的贡献就是 $b_i - a_i$，我们对这个排序，然后贪心取最大的 $n$ 个即可。

时间复杂度 $O(n\log n)$。

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 5e5 + 10;

int n, a[N << 1], b[N << 1];

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    vector<int> q;
    ll ans = 0;
    for (int i = 1; i <= 2 * n; i++) cin >> a[i] >> b[i], q.push_back(b[i] - a[i]), ans += a[i];
    sort (q.begin(), q.end());
    for (int i = q.size() - 1, j = 1; i >= 0 && j <= n; i--, j++) ans += q[i];
    cout << ans;
    return 0;
}