2010: [USACO 2023 December Contest Silver] Problem 3. Target Practice
题目描述
Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of targets located at distinct positions. Bessie starts at position and follows a string of commands, each one of L, F, or R:
- L: Bessie moves one unit to the left.
- R: Bessie moves one unit to the right.
- F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again.
If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?
输入
The first line contains and .
The next line contains the locations of the targets, distinct integers in the range .
The next line contains the command string of length , containing only the characters F, L, and R.
输出
样例输入
3 7
0 -1 1
LFFRFRR样例输出
3提示
If you make no changes to the string, Bessie will hit two targets: [expand to see graph]
Command | Position | Total Targets Hit --------+----------+------------------- Start | 0 | 0 L | -1 | 0 F | -1 | 1 F | -1 | 1 (can't destroy target more than once) R | 0 | 1 F | 0 | 2 R | 1 | 2 R | 2 | 2
If you change the last command from R to F, Bessie will hit all three targets: [expand to see graph]
Command | Position | Total Targets Hit --------+----------+------------------- Start | 0 | 0 L | -1 | 0 F | -1 | 1 F | -1 | 1 (can't destroy target more than once) R | 0 | 1 F | 0 | 2 R | 1 | 2 F | 1 | 3
SAMPLE INPUT:
1 5
0
FFFFF
SAMPLE OUTPUT:
1
If the commands are left unchanged, the only target at 0 will be destroyed. Since a target cannot be destroyed multiple times, the answer is 1.
SAMPLE INPUT:
5 6
1 2 3 4 5
FFRFRF
SAMPLE OUTPUT:
3
SCORING:
- Inputs 4-6:
- Inputs 7-15: No additional constraints.