A104184.马年冲线

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

新年钟声将近,雾港城在广场上铺了一张巨大的方格地毯。小马从 (0,0)(0,0) 出发,准备在倒计时归零前冲到烟花点 (xt,yt)(x_t,y_t)。它一边跑一边嘀咕:

只要能到达那个地方……

它手里有一段移动记录,共 nn 步,按顺序执行:

  • U(x,y)(x,y+1)(x,y)\rightarrow(x,y+1)
  • D(x,y)(x,y1)(x,y)\rightarrow(x,y-1)
  • L(x,y)(x1,y)(x,y)\rightarrow(x-1,y)
  • R(x,y)(x+1,y)(x,y)\rightarrow(x+1,y)

但这段记录里可能夹杂了“手滑”。你最多可以进行 kk 次撤销:
每次撤销可以选择任意一个位置的移动,并将该步从序列中删除(其余步保持原相对顺序执行)。

请你输出:要使小马最终恰好停在 (xt,yt)(x_t,y_t),最少需要撤销多少步;如果在最多撤销 kk 步的限制下做不到,输出 -1

输入格式

第一行四个整数 n,k,xt,ytn,k,x_t,y_t
第二行一个长度为 nn 的字符串 ss,只包含 UDLR

输出格式

输出一个整数:最少撤销步数;若无法达成输出 -1

输入输出样例

  • 输入#1

    5 3 2 1
    RRUUL

    输出#1

    2

说明/提示

样例 1 说明

不撤销时终点为 (1,2)(1,2)。撤销一次 L(相当于让 xx 增加 1)与撤销一次 U(相当于让 yy 减少 1),即可到达 (2,1)(2,1),最少需要 2 次撤销。

数据范围

  • 1n2×1051\le n\le 2\times 10^5
  • 0kn0\le k\le n
  • xt,yt2×105|x_t|,|y_t|\le 2\times 10^5
首页