连着四天睡眠不好，还考了两场试，这场打的有点神志不清，完全没感觉。赛后花好长时间补完了，掉大分啊啊。
这场其实不难，虽然D1700分，E1800分，F2500分，但是感觉虚高，知道做法简单是真简单。C题前缀和，D题链表，E题构造，F题区间DP。
A. Tricky Template
题意：
给你一个整数
n
n
n 和三个字符串
a
,
b
,
c
a, b, c
a,b,c ，每个字符串由
n
n
n 个小写拉丁字母组成。
假设一个模板是由
n
n
n 个小写和/或大写拉丁字母组成的字符串
t
t
t 。如果从
1
1
1 到
n
n
n 的所有
i
i
i 都满足以下条件，则字符串
s
s
s 与模板
t
t
t 匹配：
- 如果模板中第
i
i
i 个字母是小写字母，那么
s
i
s_i
si? 必须与
t
i
t_i
ti? 相同；
- 如果模板中的第
i
i
i 个字母是小写字母，那么
s
i
s_i
si? 必须与
t
i
t_i
ti? 的小写版本不同。例如，如果模板中有字母 “A”，则不能在字符串的相应位置使用字母 “a”。
因此，如果至少有一个
i
i
i 的条件不成立，字符串就与模板不匹配。
判断是否存在模板
t
t
t ，使得字符串
a
a
a 和
b
b
b 与之匹配，而字符串
c
c
c 不匹配。
思路：
如果看第
i
i
i 个位置，因为要保证
t
i
t_i
ti?和
a
i
b
i
a_i b_i
ai?bi?都匹配，所以如果
a
i
=
b
i
a_i=b_i
ai?=bi?，
t
i
t_i
ti?必然是小写字母，否则
t
i
t_i
ti?必然是大写字母。因此我们只需要知道
t
t
t 串和
c
c
c 串是否匹配即可，如果有一个位置不匹配，就说明可以找到，否则不能。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int T,n;
//a b相同 则c不能相同
//a b不同 则c不能与其中一个相同
int main(){
cin>>T;
while(T--){
cin>>n;
string a,b,c;
cin>>a>>b>>c;
bool f=true;
for(int i=0;i<n;i++)
if(!(a[i]==c[i] || b[i]==c[i]))
f=false;
puts((f)?"NO":"YES");
}
return 0;
}
B. Forming Triangles
你有
n
n
n 根木棒，编号从
1
1
1 到
n
n
n 。第
i
i
i 根木棒的长度是
2
a
i
2^{a_i}
2ai? 。
你想从给定的
n
n
n 根小木棍中选出3根小木棍，并用这些小木棍作为三角形的边，组成一个非退化三角形。如果一个三角形的面积严格地大于
0
0
0 ，那么这个三角形就叫做非退化三角形。
您必须计算选择恰好
3
3
3 根小棒以便用它们组成三角形的方法的数量。注意，选择木条的顺序并不重要（例如，选择第
1
1
1、第
2
2
2 和第
4
4
4 木条与选择第
2
2
2 、第
4
4
4 和第
1
1
1 木条是一样的）。
思路：
如果是非退化三角形，那么必然满足两边之和大于第三边（或者说最小两边之和大于最大边）。
假如三条边边长分别为
2
a
2
b
2
c
2^a 2^b 2^c
2a 2b 2c，并且保证
a
≤
b
≤
c
ale ble c
a≤b≤c，那么可以讨论一下能组成三角形的情况：
-
a
<
b
<
c
alt blt c
a<b<c，此时一定不可能产生三角形
-
a
<
b
=
c
alt b= c
a<b=c，此时一定不可能产生三角形
-
a
=
b
<
c
a= blt c
a=b<c，此时一定可以产生三角形
-
a
=
b
=
c
a= b= c
a=b=c， 此时一定可以产生三角形
因此不难看出，我们可以枚举a，b一定等于a，这时去累加合法的c的个数（也就是小于a的所有边的个数），因为长度一样 编号不一样也算不同的情况，所以ab的情况就是从长为a的边的总个数里选两个分别为a b，这就用到了组合数学。
具体来说，枚举a，b=a，如果边长为a的边数量超过了2，那么可以用上面的第三种情况来算，答案累加
C
c
n
t
a
2
?
c
n
t
c
C_{cnt_a}^2 * cnt_c
Ccnta?2??cntc?，如果数量超过了3，就可以用第四种情况来算，答案累加
C
c
n
t
a
3
C_{cnt_a}^3
Ccnta?3?
code：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int T,n,a[maxn];
int main(){
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1,greater<int>());
//C(cnt,3)+C(cnt,2)*(n-i)
ll ans=0;
for(int i=1,cnt;i<=n;i++){
cnt=1;
while(a[i]==a[i+1] && i<n){
i++;
cnt++;
}
if(cnt>=3)ans+=1ll*cnt*(cnt-1)*(cnt-2)/6;
if(cnt>=2)ans+=1ll*cnt*(cnt-1)/2*(n-i);
}
cout<<ans<<endl;
}
return 0;
}
C. Closest Cities
题意：
数线上有
n
n
n 座城市， 第
i
i
i 座城市位于点
a
i
a_i
ai? 。城市的坐标按升序排列，所以是
a
1
<
a
2
<
?
<
a
n
a_1 lt a_2 lt dots lt a_n
a1?<a2?<?<an? 。
两个城市
x
x
x 和
y
y
y 之间的距离等于
∣
a
x
?
a
y
∣
|a_x - a_y|
∣ax??ay?∣ 。
对于每个城市
i
i
i ，我们可以定义最近的个城市
j
j
j ，即
i
i
i 和
j
j
j 之间的距离不大于
i
i
i 和其他城市
k
k
k 之间的距离。例如，如果这些城市都位于点
[
0
,
8
,
12
,
15
,
20
]
[0, 8, 12, 15, 20]
[0,8,12,15,20] ，那么
- 距离城市
1
1
1 最近的城市是城市
2
2
2 ；
- 距离城市
2
2
2 最近的城市是城市
3
3
3 ；
- 距离城市
3
3
3 最近的城市是城市
4
4
4 ；
- 离城市
4
4
4 最近的城市是城市
3
3
3 ；
- 离城市
5
5
5 最近的城市是城市
4
4
4 。
这些城市的定位方式使得每个城市的最近城市都是唯一的。例如，城市不可能位于
[
1
,
2
,
3
]
[1, 2, 3]
[1,2,3] 点，因为这意味着城市
2
2
2 有两个最近的城市（
1
1
1 和
3
3
3 ，两者的距离都是
1
1
1 ）。
您可以在城市之间旅行。假设您目前在城市
x
x
x 。那么您可以执行以下操作之一：
- 前往任何其他城市
y
y
y ，支付
∣
a
x
?
a
y
∣
|a_x - a_y|
∣ax??ay?∣ 金币；
- 前往距离
x
x
x 最近的城市，支付
1
1
1 金币。
您会收到
m
m
m 个询问。在每个查询中，您将得到两个城市，您必须计算从一个城市到另一个城市所需的最少金币数。
思路：
淦，一开始写的莫队，写了半天一看是个前缀和。。。
从l到r城市一定是不走回头的，也就是说，一定是
l
→
l
+
1
→
.
.
.
→
r
l
ightarrow l+1
ightarrow...
ightarrow r
l→l+1→...→r 这样一条单向的路径。那么从 l 到 r 的路径可以通过 1到r的路径 减去 1到l的路径 得到，可以前缀和。
某个城市的最近城市这个关系可以抽象地看作一个单向边关系，也就是说，a的最近城市是b，那么b的最近城市不一定是a。所以从r城市走到l城市的长度和从l到r城市是不一样的，所以还需要处理反向的情况，也就是搞个反向前缀和（后缀和）。
code：
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=1e5+5;
int T,n,m,a[maxn];
int s1[maxn],s2[maxn];
inline int getv(int i,int x){//i->i+x
return (abs(a[i+x]-a[i])<abs(a[i]-a[i-x]) || i==1 || i==n)?1:abs(a[i+x]-a[i]);
}
int main(){
cin>>T;
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=2;i<=n;i++)
s1[i]=s1[i-1]+getv(i-1,1);
s2[n]=0;
for(int i=n-1;i>=1;i--)
s2[i]=s2[i+1]+getv(i+1,-1);
scanf("%d",&m);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
if(x<=y)printf("%d
",s1[y]-s1[x]);
else printf("%d
",s2[y]-s2[x]);
}
}
return 0;
}
D. Berserk Monsters
Monocarp 正在玩电脑游戏（又一次）。猜猜他在做什么？没错，杀怪。
一排有
n
n
n 个怪物，编号从
1
1
1 到
n
n
n 。其中
i
i
i 个怪物有两个参数：攻击值等于
a
i
a_i
ai? ，防御值等于
d
i
d_i
di? 。为了杀死这些怪物，莫诺卡普给它们施放了狂暴咒语，因此它们会互相攻击，而不是攻击莫诺卡普的角色。
战斗由
n
n
n 个回合组成。每回合都会发生以下情况：
- 首先，每个编号
i
i
i 的活着的怪物都会对左边近活着的怪物（如果存在）和右边近活着的怪物（如果存在）造成
a
i
a_i
ai? 伤害；
- 然后，每只在本回合中受到超过
d
j
d_j
dj? 伤害的活着的怪物
j
j
j 都会死亡。也就是说，当且仅当编号为
j
j
j 的怪物的防御值
d
j
d_j
dj? 小于它在本轮受到的总伤害时，它才会死亡。
计算每一轮中死亡的怪物数量。
思路：
因为每一轮都要算，而且一共n轮，做法还要求是
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 的，那么我们需要每一轮计算死掉的怪物数不能暴力枚举。
考虑到除了第一轮，后面的一轮中只有在前一轮死掉的怪物旁边的怪有可能会死，因为怪物死掉后会让两边的怪物接触。否则一个怪两边的怪没有变化，这个怪物就一直不会死（要不然一开始就死了）。
这样想的话，因为一个怪最多只会被杀死一次，杀死一次怪会带来两次检查，所以总的杀怪和查怪次数最多就是 3n 的，可以通过。
如何实现。因为要不断删掉怪物，以及查询一个怪相邻的怪，所以用双向链表来维护每个怪相邻的前后怪的位置。因为两个怪是可以同归于尽的，所以检查环节和杀怪环节不能放一块，检查的时候标记一下死掉的怪，然后再把怪杀掉，把死掉的怪的两边的怪放到下一次检查里。因为一个怪一轮中可能会被多次检查，所以用set记录要检查的怪，因为一个怪可能检查之前就似了，所以用dead数组标记一下，死掉的就不检查了。
在实现上，因为第一个怪前面和最后一个怪后面没怪，为了防止特判，所以我们可以在前后位置各加入一个没有攻击力但是防御力超强的怪梅普露（当成墙就可以了）。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int maxn=3e5+5;
typedef long long ll;
int T,n,a[maxn],d[maxn];
int pre[maxn],nxt[maxn];
set<int> ck;
int dl[maxn],cnt2;
bool dead[maxn];
int main(){
cin>>T;
while(T--){
cin>>n;
memset(dead,false,sizeof(dead));
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>d[i];
a[0]=0;
d[0]=2e9+5;
nxt[n]=0;
pre[0]=0;
cnt2=0;
for(int i=1;i<=n;i++){
ck.insert(i);
pre[i]=i-1;
nxt[i-1]=i;
}
for(int round=1;round<=n;round++){
for(auto idx:ck){
if(dead[idx])continue;
if(d[idx]<a[pre[idx]]+a[nxt[idx]]){
dl[++cnt2]=idx;
ck.clear();
for(int i=1,idx;i<=cnt2;i++){
idx=dl[i];
ck.insert(pre[idx]);
ck.insert(nxt[idx]);
nxt[pre[idx]]=nxt[idx];
pre[nxt[idx]]=pre[idx];
dead[idx]=true;
}
printf("%d ",cnt2);
cnt2=0;
}
puts("");
}
return 0;
}
E. Increasing Subsequences
构造题，这个挺有意思的，赛时也是过的比D多。
题意：
回顾一下，数组
a
a
a 的递增子序列是指在不改变其余元素顺序的情况下，通过移除某些元素而得到的序列，并且其余元素是严格递增的（即
a
b
1
<
a
b
2
<
?
<
a
b
k
a_{b_1} lt a_{b_2} lt dots lt a_{b_k}
ab1??<ab2??<?<abk?? 且
b
1
<
b
2
<
?
<
b
k
b_1 lt b_2 lt dots lt b_k
b1?<b2?< ?<bk? ）。注意，空子序列也是递增的。
给你一个正整数
X
X
X 。你的任务是找出一个长度为最多
200
200
200 的整数数组，使得它有恰好
X
X
X 个递增的子序列，或者报告说没有这样的数组。如果有多个答案，你可以打印其中任何一个。
如果两个子序列由相同的元素组成，但对应数组中的不同位置，则认为它们是不同的（例如，数组
[
2
,
2
]
[2, 2]
[2,2] 有两个不同的子序列等于
[
2
]
[2]
[2] ）。
思路：
从最简单的方式入手，只看一个递增序列，假如是
1
2
3
4
?
n
1 2 3 4cdots n
1 2 3 4? n 这样的。因为无论怎么取都是满足条件的，所以每个位置有取和不取两种情况，所以总的方法数是
2
n
2^n
2n 个（包括空子序列）。如果不包含空子序列，那么在最后面加一个1（小于等于最小值）就可以得到
2
n
2^n
2n 个。
我们肯定想要凑到
X
X
X ，所以想要弄到若干个这样的区间，而且区间之间互相不影响，然后把它们首位相连就可以了。不影响也好搞，只要让后一个区间的最大值小于前一个区间的最小值即可。比如4 5 6 7 4 1 2 3 1，它的方法数就是
2
4
+
2
3
2^4+2^3
24+23 。
但是题目要求长度小于200，凑得区间长度最多会有60，60+59+58+…早爆了。考虑把几个区间压缩一下，前面部分共用。
具体来说，最前面有个
1
2
3
4
?
n
1 2 3 4cdots n
1 2 3 4? n，如果在后面加入一个
x
x
x
(
1
≤
x
≤
n
)
(1le xle n)
(1≤x≤n)，那么它可以用到前面的 1 ~ x-1，这就实现了 1 ~ x-1部分的共用。或者说通过选取这个 x 凑出的合法递增子序列必须选上这个 x，同时最前面的前x-1个数可以随便选，那么总的个数就是
2
x
?
1
2^{x-1}
2x?1个。后面x递减地加入就可以保证加入的x之间互相不影响。
所以先找到最前面那个递增序列，然后通过
X
X
X 的余数的二进制找后面插入什么x，之后把构造的数列输出即可。
code：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1005;
int T;
ll x;
int a[maxn],cnt,len;
int main(){
cin>>T;
while(T--){
cin>>x;
cnt=len=0;
int t=60;
while(x<(1ll<<t))t--;
a[++cnt]=t;
x-=(1ll<<a[cnt]);
len+=a[cnt];
for(int i=61;i && x;i--){
if(x>=(1ll<<(i-1))){
x-=(1ll<<(i-1));
a[++cnt]=i;
len++;
}
}
printf("%d
",len);
for(int i=1;i<=a[1];i++){
printf("%d ",i);
}
for(int i=2;i<=cnt;i++)
printf("%d ",a[i]);
puts("");
}
return 0;
}
思路2：
假如序列前面的部分的总的递增子区间个数为
f
f
f。
-
如果我们加入一个最小值，这个最小值不会对前面任何序列产生合法子序列，所以会得到
f
+
1
f+1
f+1 个合法子序列。
-
如果我们加入一个比最大值还大的数，这个数可以和前面任何序列产生一个新的合法子序列，所以会得到
2
?
f
2*f
2?f 个合法子序列。
其实就相当于通过上面这两个操作，问能不能凑出
X
X
X 了。对要凑的一个数x，如果x为奇数，那么它一定是由操作1得到的，否则如果x为偶数，那么它一定是由操作2得到的，一直推到1（空序列也算一个，所以x=1时说明序列已经空了），之后再推回来，递归。
code：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1005;
int T;
ll x;
int maxx,minn,a[maxn],cnt;
void solve(ll x){
if(x==1)return;//x==1时就是空序列了，可以进行回溯了
solve((x&1)?x-1:x/2);
if(x&1)a[++cnt]=minn;
else a[++cnt]=++maxx;
}
int main(){
cin>>T;
while(T--){
cin>>x;
cnt=0;minn=maxx=1;
solve(x);
printf("%d
",cnt);
for(int i=1;i<=cnt;i++)
printf("%d ",a[i]);
puts("");
}
return 0;
}
F. Replace on Segment
题意：
给你一个数组
a
1
,
a
2
,
…
,
a
n
a_1, a_2, dots, a_n
a1?,a2?,…,an? ，其中每个元素都是一个从
1
1
1 到
x
x
x 的整数。
你可以多次对它进行下面的操作：
- 选择三个整数
l
l
l 、
r
r
r 和
k
k
k ，使得
1
≤
l
≤
r
≤
n
1 le l le r le n
1≤l≤r≤n 、
1
≤
k
≤
x
1 le k le x
1≤k≤x 和每个元素
a
i
a_i
ai? ，使得
l
≤
i
≤
r
l le i le r
l≤i≤r 与
k
k
k 不同。然后，对于每个
i
∈
[
l
,
r
]
i in [l, r]
i∈[l,r] ，用
k
k
k 替换
a
i
a_i
ai? 。
换句话说，在数组中选择一个子段，并从
1
1
1 到
x
x
x 中选择一个不在该子段中出现的整数，然后用该整数替换子段中的每个元素。
您的目标是使数组中的所有元素相等。最少需要进行多少次操作？
思路：
2500分的区间DP，队友说不难，但是我不好说，我看不懂。介绍一个
O
(
n
4
)
O(n^4)
O(n4) 的区间DP做法。
因为题目说了
n
n
n 虽然总个数最多为500，但是每个样例
n
n
n 的个数最多为100，所以
O
(
n
4
)
O(n^4)
O(n4) 最多会跑到5e8，3s时限是可以跑得动的。
我们可以进行一种操作，就是选择一个区间
[
l
,
r
]
[l,r]
[l,r]，保证没有k颜色，使得区间所有元素变为k颜色，想要让dp去通过这个操作由其他状态来推到其他状态，显然一个dp是不太够用的，因为我们不知道一个区间到底有没有k这个颜色。所以设置两个dp数组，分别为
d
p
1
[
l
]
[
r
]
[
k
]
dp1[l][r][k]
dp1[l][r][k] 和
d
p
2
[
l
]
[
r
]
[
k
]
dp2[l][r][k]
dp2[l][r][k] 前者表示把
[
l
,
r
]
[l,r]
[l,r] 区间所有颜色变为k的操作次数，后者表示把
[
l
,
r
]
[l,r]
[l,r] 区间所有颜色变为非k的操作次数。因此就可以通过题目给的操作从dp2来推dp1了，也就是从
d
p
1
[
l
]
[
r
]
[
s
]
(
s
!
=
k
)
→
d
p
2
[
l
]
[
r
]
[
k
]
→
d
p
1
[
l
]
[
r
]
[
k
]
dp1[l][r]▼显示quad (s!=k)
ightarrow dp2[l][r][k]
ightarrow dp1[l][r][k]
dp1[l][r]▼显示(s!=k)→dp2[l][r][k]→dp1[l][r][k]（其实这一步本质上相当于
d
p
1
[
l
]
[
r
]
[
s
]
(
s
!
=
k
)
→
d
p
1
[
l
]
[
r
]
[
k
]
dp1[l][r]▼显示quad (s!=k)
ightarrow dp1[l][r][k]
dp1[l][r]▼显示(s!=k)→dp1[l][r][k]，因此不会出现循环的可能，也就是不可能dp1修改了dp2修改了dp1再修改了dp2…，不过两非k颜色的区间的合并需要用到dp2，所以dp2不能被优化掉）
-
d
p
1
[
l
]
[
r
]
[
k
]
dp1[l][r][k]
dp1[l][r][k] 相当于有两种选择。一种是枚举断点将两区间dp1合并。另一种是保证区间无k，并对区间进行一次操作，也就是从
d
p
2
[
l
]
[
r
]
[
k
]
dp2[l][r][k]
dp2[l][r][k] 推过来，
d
p
1
[
l
]
[
r
]
[
k
]
=
d
p
2
[
l
]
[
r
]
[
k
]
+
1
dp1[l][r][k]=dp2[l][r][k]+1
dp1[l][r][k]=dp2[l][r][k]+1 。
-
而
d
p
2
[
l
]
[
r
]
[
k
]
dp2[l][r][k]
dp2[l][r][k] 同样有两种选择。第一种是枚举断点，合并两区间dp2。第二种是从
d
p
1
[
l
]
[
r
]
[
s
]
(
s
!
=
k
)
dp1[l][r]▼显示quad (s!=k)
dp1[l][r]▼显示(s!=k)推过来。
因此枚举区间长度和区间左端点，这样就有了
l
l
l 和
r
r
r，然后枚举断点和颜色，来用区间合并的方式算出dp1和dp2。这时得到的
d
p
1
[
l
]
[
r
]
[
k
]
dp1[l][r][k]
dp1[l][r][k] 同时相当于
d
p
2
[
l
]
[
r
]
[
s
]
(
s
!
=
k
)
dp2[l][r]▼显示quad (s!=k)
dp2[l][r]▼显示(s!=k)。枚举
d
p
2
[
l
]
[
r
]
[
k
]
=
m
i
n
{
d
p
2
[
l
]
[
r
]
[
k
]
,
d
p
1
[
l
]
[
r
]
[
s
]
(
s
!
=
k
)
}
dp2[l][r][k]=min{dp2[l][r][k],dp1[l][r]▼显示quad (s!=k)}
dp2[l][r][k]=min{dp2[l][r][k],dp1[l][r]▼显示(s!=k)}。之后再把dp2转化成dp1即可。
这里可以加一步优化：用
x
l
xl
xl 数组表示前 i 个颜色中dp1最小的那个，用
x
r
xr
xr 数组表示 i 后面的颜色中dp1最小的颜色。这样就变成了
d
p
2
[
l
]
[
r
]
[
k
]
=
m
i
n
{
d
p
2
[
l
]
[
r
]
[
k
]
,
x
l
[
k
?
1
]
,
x
r
[
k
+
1
]
}
dp2[l][r][k]=min{dp2[l][r][k],xl[k-1],xr[k+1]}
dp2[l][r][k]=min{dp2[l][r][k],xl[k?1],xr[k+1]}，这样就不用每次都去枚举s了。
code：
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=105;
const int inf=1e9;
int T,n,x,a[maxn];
int dp1[maxn][maxn][maxn],dp2[maxn][maxn][maxn];
int main(){
cin>>T;
while(T--){
cin>>n>>x;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
for(int k=1;k<=x;k++){
dp1[i][i][k]=1;
dp2[i][i][k]=0;
}
dp1[i][i][a[i]]=0;
dp2[i][i][a[i]]=1;
}
for(int len=2;len<=n;len++){
for(int l=1,r;(r=l+len-1)<=n;l++){
for(int k=1;k<=x;k++){
dp1[l][r][k]=dp2[l][r][k]=inf;
for(int t=l;t<r;t++){
dp1[l][r][k]=min(dp1[l][r][k],dp1[l][t][k]+dp1[t+1][r][k]);
dp2[l][r][k]=min(dp2[l][r][k],dp2[l][t][k]+dp2[t+1][r][k]);
}
}
int xl[maxn],xr[maxn];//变前面其他颜色的最小操作次数，以及后面
xl[0]=xr[x+1]=inf;
for(int c=1;c<=x;c++)
xl[c]=min(xl[c-1],dp1[l][r][c]);
for(int c=x;c>=1;c--)
xr[c]=min(xr[c+1],dp1[l][r][c]);
for(int c=1;c<=x;c++){
dp2[l][r][c]=min(dp2[l][r][c],min(xl[c-1],xr[c+1]));
dp1[l][r][c]=min(dp1[l][r][c],dp2[l][r][c]+1);
}
}
}
int ans=inf;
for(int i=1;i<=x;i++)
ans=min(ans,dp1[1][n][i]);
cout<<ans<<endl;
}
return 0;
}