「签到题」 CF1354F Summoning Minions

upd: 改了错别字 旁白：这个 F 怎么也这么签啊？ ____ ~~盲猜这个游戏是炉石~~ 赛场上一眼背包，发现大概是 $O(\max\{a_i,b_i\}\cdot nk^2)$ 的就弃掉了。然后考虑贪心。考虑这么一个比较自然的想法，就是先找出前 $k-1$ 个来，然后 $n-k$ 个加一个删一个，最后再把 $1$ 个加进来。不难知道这样一定可以做出最优的决策。 那么考虑怎么搞这三部分。 第一部分可以背包，$f_{i,j}$ 表示前 $i$ 个随从找出了 $j$ 个放进第一个部分的最大价值。注意这个地方有一个代价提前计算的思想。就是说考虑如果把随从 $z$ 在前 $k-1$ 个里的第 $j$ 位召唤出来，那么放到后面应该是产生 $(k-1)\cdot b_z$ 的贡献，现在就只有 $(j-1)\cdot b_z$ 的贡献，于是有 $$ f_{i,j}=\max\left\{f_{i-1,j-1}-(k-j)\cdot b_i+a_i,f_{i-1,j}\right\} $$ 然后一个小细节就是显然必须要按照 $a_i$ 降序且 $b_i$ 升序来进行排序，同时由于是对 $a_i$ 来 $dp$，所以应该让 $b_i$ 为第一关键字。 第二、三部分考虑合起来做。即考虑枚举最后一个随从，那么剩下的元素就一定是按照 $b_z$ 升序排序，因为他们加入就会被立即删掉。 但这样会发现 `WA ON 2`。冷静一下就会发现最后一个元素由于也要计算其 $a_i$ ，所以应该和前面的 $k-1$ 个等价，换言之最后在剩下的元素里贪出最后一个位置放的随从是不对的。观察数据范围很小，于是可以枚举最后一个位置放哪个随从，对于不同的最后一个位置分别做前两部分。不难知道这样是对的。 这样最后复杂度 $O(T\cdot n^2k)$，可以通过本题。 瞎扯1： 这么看来这个复杂度还是很合理的？$75^4$ 大概在 $3e7$ 左右。 瞎扯2： 实际上场上写的时候并没有细想第一部分到底该怎么排序，那反正就是要么 $a_i$ 做第一关键字要么 $b_i$ 做第一关键字。看着当时似乎没多少人过 F 就选择 $2!$ 枚举了一下这两种排法（ 瞎扯3: 为什么这场比较正常的题 (E 以及 E 之后) 都这么无聊但是代码这么麻烦？反正我写的挺麻烦的。 ```cpp int T ; struct minion{ int a, b, id ; }base[N], tmp[N] ; int n, k ; int cnt ; int ans ; int lst ; int ud[N] ; int fin[N] ; int quq[N] ; int qaq[N] ; int qwq[N] ; int f[N][N] ; int pre[N][N] ; bool comp(minion x, minion y){ return x.b == y.b ? x.a > y.a : x.b < y.b ; } bool cop(minion x, minion y){ return x.b < y.b ; } int main(){ cin >> T ; while (T --){ cin >> n >> k ; ans = 0 ; for (int i = 1 ; i <= n ; ++ i) base[i].a = qr(), base[i].id = i, base[i].b = qr() ; sort(base + 1, base + n + 1, comp) ; fill(fin, fin + n + 1, 0) ; for (int z = 1 ; z <= n ; ++ z){ memset(f, -63, sizeof(f)) ; fill(ud, ud + n + 1, 0) ; f[0][0] = 0 ; cnt = 0 ; for (int i = 1 ; i <= n ; ++ i){ for (int j = 0 ; j <= k - 1 ; ++ j){ int tmp = base[i].b * (j - k) ; if (!j || i == z) f[i][j] = f[i - 1][j], pre[i][j] = 0 ; else { // cout << i << " " << j << " " << f[i - 1][j] << " " << f[i - 1][j - 1] + base[i].a + tmp << '\n' ; if (f[i - 1][j] > f[i - 1][j - 1] + base[i].a + tmp) f[i][j] = f[i - 1][j], pre[i][j] = 0 ; else f[i][j] = f[i - 1][j - 1] + base[i].a + tmp, pre[i][j] = 1 ; } } } int p = n, q = k - 1 ; while (p && q){ if (!pre[p][q]) -- p ; else qaq[q] = p, ud[base[p].id] = 1, -- q, -- p ; } // debug(q) ; debug(ud, 1, n) ; for (int i = 1 ; i <= n ; ++ i) if (!ud[base[i].id] && i != z) qwq[++ cnt] = i ; int res = 0, gz = 0 ; for (int j = 1 ; j <= cnt ; ++ j) tmp[++ gz] = base[qwq[j]] ; sort(tmp + 1, tmp + gz + 1, cop) ; for (int j = 1 ; j <= gz ; ++ j) res += (k - 1) * tmp[j].b ; for (int j = 1 ; j <= k - 1 ; ++ j) res += base[qaq[j]].a + (j - 1) * base[qaq[j]].b ; res += base[z].a + base[z].b * (k - 1) ; debug(res) ; // for (int j = 1 ; j <= k - 1 ; ++ j) // cout << base[qaq[j]].id << " \n"[j == k - 1] ; if (res >= ans) { ans = res, lst = z ; for (int i = 1 ; i <= k - 1 ; ++ i) quq[i] = qaq[i] ; for (int i = 1 ; i <= cnt ; ++ i) fin[i] = qwq[i] ; } } // debug(ans) ; // debug(cnt) ; cout << k + 2 * cnt << '\n' ; for (int i = 1 ; i <= k - 1 ; ++ i) cout << base[quq[i]].id << ' ' ; for (int i = 1 ; i <= cnt ; ++ i) cout << base[fin[i]].id << ' ' << -base[fin[i]].id << ' ' ; cout << base[lst].id << "\n" ; } return 0 ; }/* 1 5 2 3538 43176 24258 77210 92123 70606 44495 37855 65913 67119 291273 8 3 4 -4 2 -2 1 -1 5 4 2 -2 5 -5 1 -1 3 */ ```