ABC366F Maximum Composition
Tag：数学、DP
题目描述
给定 \(N\) 个线性方程，其中 \(f_i(x) = A_ix+B_i\)。
现在从这些线性方程中选出 \(K\) 个， 求 \(f_{p1}(f_{p2}(\cdots f_{pk}(1) \cdots))\) 的最大可能值。
数据说明：
\(1 \leq N \leq 2 \times 10^{5}\)
\(1 \leq K \leq \text{min}(N,10)\)
\(1 \leq A_i,B_i \leq 50 (1\ \leq i \leq N)\)
分析
直接看这个问题我们可能不太好入手， 我们尝试把问题简化一下， 如果已经知道了最后要选哪 \(k\) 个， 我们要怎么做。 这样似乎还是不够好入手， 我们直接化简到，对于给定的一个 \(f_i(x)\) 和 \(f_j(x)\)， 要怎么算才能最大化答案？
既然只有两个函数，也就只有两种做法， 分别是 \(f_i(f_j(x))\) 和 \(f_j(f_i(x))\)。 尝试把 \(A,B\) 代入，可以分别得到 \(A_iA_jx + A_iB_j + B_i\) 和 \(A_iA_jx + A_jB_i + B_j\)。 发现不同的位置只有后两项，也就是说大小和 \(x\) 是无关的。 我们列一个不等式为：
\[\begin{equation}
A_iB_j + Bi \lt A_jB_i + B_j
\end{equation}\]
移项处理可以得到：
\[\begin{equation}
\frac{A_i-1}{Bi} \lt \frac{A_j-1}{B_j}
\end{equation}\]
于是我们可以按照这个式子对函数进行排序。
之后我们定义一个 \(dp[i][j]\)， 其意义为前 \(i\) 个函数里已经选了 \(j\) 个时的最大答案， 从前向后转移就可以了， 最后 \(dp[n][k]\) 就是我们要求的答案。
代码实现
void NeverSayNever() {
int n, k; cin >> n >> k;
vector<PII> vec(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> vec[i].first >> vec[i].second;
}
std::sort(vec.begin() + 1, vec.end(), [](PII x, PII y) {
return (x.first - 1) * y.second < (y.first - 1) * x.second;
});
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
dp[i][0] = dp[i - 1][0];
for (int j = 1; j <= k; ++j) {
dp[i][j] = max(dp[i - 1][j], vec[i].first * dp[i - 1][j - 1] + vec[i].second);
}
}
cout << dp[n][k] << endl;
}
日志
本页面创建于 2024/09/02 13:43