题目大意
有 \(n\) 场\(\textbf{按顺序}\)的比赛，第 \(i\) 场比赛有表现分 \(p_i\)。参加第 \(i\) 场比赛后你的分数 \(r\) 将变为 \(r\times(1-k)+k\times p_i\)。你可以选择最多 \(m\) 场比赛不参加。给定初始分数 \(r_0\) 和参数 \(k\)。问经过至少 \(n-m\) 场比赛后，分数最高是多少。
题解做法
根据数据范围 \(k\geq0.1\), 经过至多 200 场后之前的分数影响将在精度误差之内, 故只需要考虑最后 \(\min(m+200,n)\) 场比赛即可.
场上某大佬做法（可忽略 k 范围）
const int N = 1e6 + 5;
ll a[N];
db k, p[N];
#define vt vct<db>
vt dfs (int l, int r)
{
if (l == r) rty {0, k * a[l]};
int m = l + r >> 1;
vt L = dfs (l, m);
vt R = dfs (m + 1, r);
int i = 0, j = 0;
vt ans = {0};
while (i + 1 < L.sz && j + 1 < R.sz)
{
if (L[i] * p[j + 1] + R[j + 1] > L[i + 1] * p[j] + R[j])
j++, ans.pb (L[i] * p[j] + R[j]);
else
i++, ans.pb (L[i] * p[j] + R[j]);
}
while (i + 1 < L.sz ) i++, ans.pb (L[i] * p[j] + R[j]);
while (j + 1 < R.sz ) j++, ans.pb (L[i] * p[j] + R[j]);
rty ans;
}
void solve()
{
cin >> n >> m >> k >> x;
p[0] = 1;
fo (i, 1, n) p[i] = p[i - 1] * (1 - k), cin >> a[i];
vt rp = dfs (1, n);
db ans = 0;
fo (i, n - m, n)
{
ans = max (ans, x * p[i] + rp[i]);
// print (x * p[i] + rp[i])
}
sp (12);
ANS;
rty;
}
用类似归并排序的方式来求区间内选择 \(1\sim len\) 场的最大得分.
分析: 在相同场次下, 不同的选取方式大小关系与初始分数无关. 基于原始 dp \(f_{i,j}\) 表示前 \(i\) 场, 选了 \(j\) 场参加的最大得分. 寻找性质快速合并.
下面来证明正确性：
