T1：最长倍数序列
本题难度中等，先把 \(a\) 从小到大排序。dp[i] 表示以 \(a_i\) 结尾的倍数序列。转移如下：
- 只有 \(a_i\)，对应长度 \(dp[i] = 1\)
- 上一个数是 \(a_j (1 \leqslant j \leqslant i-1)\)，若 \(a_j\) 是 \(a_i\) 的约数，就更新 \(dp[i] = \max(dp[i], dp[j]+1)\)
最终答案就是所有 \(dp\) 的最大值
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(n);
rep(i, n) cin >> a[i];
sort(a.begin(), a.end());
vector<int> dp(n, 1);
int maxSize = 1;
for (int i = 1; i < n; ++i) {
rep(j, i) {
if (a[i]%a[j] == 0) {
dp[i] = max(dp[i], dp[j]+1);
}
}
if (dp[i] > maxSize) {
maxSize = dp[i];
}
}
cout << maxSize << '\n';
return 0;
}
T2：大胃王比赛
本题难度较大，随着修行次数增多，成绩一定不会变差，所以可以二分答案。对于成绩 \(x\)，计算要使得每名队员的时间都小于等于 \(x\)，所需的最小修行次数。对每人计算要让 \(A_iF_i \leqslant x\)，\(A_i\) 需要减少的次数。最后判断修行总次数是否小于等于 \(K\)。
因为最终成绩是所有人成绩的最大值，所以每次选 \(F\) 最大的人修行的贪心算法是错误的。改成最终成绩是总和就可以变成一个贪心题。
代码实现
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n; ll k;
cin >> n >> k;
vector<int> a(n), f(n);
rep(i, n) cin >> a[i];
rep(i, n) cin >> f[i];
ll wa = -1, ac = 1e12;
while (ac-wa > 1) {
ll wj = (ac+wa)/2;
bool ok = [&]{
ll s = 0;
rep(i, n) s += max(0ll, a[i]-wj/f[i]);
return s <= k;
}();
(ok ? ac : wa) = wj;
}
cout << ac << '\n';
return 0;
}