【FJ互测】【bzoj3704】昊昊的机油之GRST

2014年7月12日1,2770

题目描述(grst.c/cpp/pas)

昊昊有个好机油,他就是传说中的着力点。现在昊昊获得了一份长度为n的GRST牌(mod 4 意义下),打算作为送给好机油的生日礼物(不是在2月的么)。但是,昊昊深知他的机油是个神犇,作为数字控的他,只会喜欢特定的序列。但是昊昊不怕,他可以使用一次菲亚特(他的机油最喜欢的大招),将一段区间内的数字全部+1,若某个数字为3,则+1后变为0。但昊昊的神力是有限的,问从初始序列a到达最终序列b,最少需要使用多少次菲亚特。

输入格式(grst.in)

从stdin读入

第一行一个正整数n,表示GRST长度。

接下来两行,每行n个值,分别表示ai bi。

输出格式(grst.out)

从stdout读入

仅一个数,即最少需要使用多少次菲亚特。

样例输入

3

0 2 1

1 0 2

样例输出

2

数据规模与约定

样例说明:第一次对区间[1,2] 使用菲亚特。第二次对区间[2,3] 使用菲亚特。

测试点编号 N
1 5
2 10
3 100
4 1000
5 10000
6 100000
7 1000000
8 1000000
9 10000000
10 10000000

 

0<=ai,bi<=3

 

时间限制

1s

内存限制

1G

题解

记录 f[i][j]为做到第 i 位的高度为 j 的最小代价,dp60-80分

先考虑构造合法解,每次都对一个后缀加上一定的值。

对于合法解的优化,我们可以在差分序列上选择一位进行-4 操 作,相当于对后缀-4,可以节省的代价根据(当前位-上一位)决定。

所以,我们先对于差分序列中为 3 的位置考虑-4,可以节省 3 的 代价。

剩下的依次贪心,注意判断序列合法性