第一次尝试 Codeforces 的虚拟参赛 awa,感觉还不错,可以把之前的比赛拿来练练
反正又不会掉分
但是这场 Div2 好难啊
Part1. 题意
中文题意
给出一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$ 以及另一个数列 $b_1,b_2,…,b_n$。
你可以进行若干次操作:选定一个 $i$,将 $a_i$ 增加 $1$,花费为 $b_i$。(可以对同一个 $i$ 进行多次操作)
要求最后的数列 $a_1,a_2,…,a_n$ 满足对于任意的 $i(2\leq i\leq n)$ 有 $a_{i-1}\not=a_i$。求最小的花费。
多组询问。
数据规模
$1\leq n\leq3\times 10^5$,且满足所有询问的 $n$ 之和不超过 $3\times10^5$。
$1\leq a_i,b_i\leq10^9$。
保证答案不超过 $10^{18}$。
Part2. 题解
卡在 D题 有益于身心健康
首先我们发现这道题没法贪心……然后基本上就知道这道题是一个 动态规划(基本上嘛)
于是就有了一个非常非常非常 Easy 的思路,f[i][j]
表示第 i
个数为 j
时,使前 i
个数满足条件(相邻两数不同)的最小花费。而且有一个非常明显的转移:
1 | f[i][j] = min{ f[i-1][k] + B[i]*(j-A[i]) } |
但是我们发现,这个状态定义的第二维是 $10^9$…… 尝试着去优化,发现优化不了 qwq(比赛时思路就此停滞)
最后瞄了一眼题解,发现这样一个结论:每一个数最多增加 2 次。
设数字
A[i]
增加后变为A'[i]
。如果一个数
A[i]
增加了 3 次,那么A'[i+1]
和A'[i-1]
中一定有一个数等于A'[i]-1
(也就是增加后比A'[i]
小 1),不然A[i]
就可以只增加 2。那么不妨设以下三种情况:
A'[i-1]!=A[i] , A'[i+1]=A'[i]-1=A[i]+2
,那么发现A[i]
可以不增加;A'[i-1]=A[i] , A'[i+1]=A'[i]-1=A[i]+2
,那么发现A[i]
可以只增加 1;于是贪心发现
A[i]
没有必要增加超过 2.
于是我们改变状态定义,f[i][j]
表示第 i
个数字增加 j
,前 i
个数字满足条件的最小花费。转移就是:
1 | f[i][j] = min{ f[i-1][k] + j*B[i] } |
其中,根据上面的论证,可以知道 j=0~2,所以就可以 AC 了。
Part3. 源代码
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com,欢迎提问~