2019.9.15 校内模拟赛

前言

分数不算高,100 + 37 + 0,但为什么就排到靠前了??

T1 – Snakes

原题地址

一句话题面:$n$ 个数分成 $k+1$ 组,要求每组最大值和每个值的差之和的总和最少。

挺水的一个 DP,转移有修改捕网大小和不修改两种,不修改用 ST 表求最大值记录一下最后一段的代价,修改直接转移。

$f[i][j]$ 表示当前第 $i$ 只蛇,已经修改过 $j$ 次的最小代价。

$$f\lbrack i\rbrack\lbrack j\rbrack=min\left\{\begin{array}{l}\begin{array}{l}f\lbrack i-1\rbrack\lbrack j-1\rbrack\;(j>0 时)\\f\lbrack k-1\rbrack\lbrack j-1\rbrack+max(s\lbrack k\rbrack,s\lbrack k+1\rbrack,……,s\lbrack i-1\rbrack,s\lbrack i\rbrack)\ast(i-k+1)-(sum\lbrack i\rbrack-sum\lbrack k-1\rbrack)\;(k=1\sim i-1)\end{array}\end{array}\right.$$

不过细节挺多,调了很久,具体看代码

T2 – I Would Walk 500 Miles

原题地址

因为懒贴个 LG 题解上来

考的时候没想到,有大佬在考场上直接推出结论了 Orz

T3 -Valleys

原题地址

直接贴题解吧

Image Source : https://blog.csdn.net/qq_39972971/article/details/89296244

评论

  1. T2链接给错了…

    1月前
    2019-9-21 20:22:40

发送评论


				
上一篇
下一篇