OI - Make The Fence Great Again(Codeforces) | Lucky_Glass's Blog
0%

OI - Make The Fence Great Again(Codeforces)

第一次尝试 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
2
f[i][j] = min{ f[i-1][k] + B[i]*(j-A[i]) }
//k!=j; 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
2
f[i][j] = min{ f[i-1][k] + j*B[i] }
//0<=k<=2; A[i-1]+k!=A[i]+j

其中,根据上面的论证,可以知道 j=0~2,所以就可以 AC 了。


Part3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=3e5;

int n,It;
int Ia[N+3],Ib[N+3];
ll Ef[N+3][10];

int main(){
scanf("%d",&It);
while(It--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&Ia[i],&Ib[i]);
Ef[1][0]=0;Ef[1][1]=Ib[1];Ef[1][2]=Ib[1]*2;
for(int i=2;i<=n;i++)
for(int j=0;j<3;j++){
Ef[i][j]=(1ll<<62);
for(int k=0;k<3;k++)
if(Ia[i-1]+k!=Ia[i]+j)
Ef[i][j]=min(Ef[i][j],Ef[i-1][k]+j*Ib[i]);
}
printf("%lld\n",min(Ef[n][0],min(Ef[n][1],Ef[n][2])));
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问~