积木每个单位的高度为1或2,拼接后不能超过3,所以耦合需要1和2的组合,即不能同时为2。
由于数据较小,因此模拟即可。判断串s的一个后缀是否能够与t的前缀耦合,即判断这两部分是否同时出现了2。
因此时间复杂度为O(N2)
NN有一种锯齿状的积木,这种积木比较长,但是每个单位长度的高度是相等的高度为 1 或者 2。
现在NN拿出了两块长度分别为n和 m 的积木,她现在想把这两块积木拼接在起,即使中间有空隙也没有关系。
但是拼接后的积木的高度要不超过 3,请你帮助NN计算在满足这个前提下拼接后的积木的长度最短可以是多少。
注:本题正解应当考虑积木可以翻转,但是考场上不翻转积木反而AC了,所以本题应当额外加上“不能够翻转积木”的条件
第一行给出两个正整数 n,m,代表第一块和第二块积木的长度
第二行给出 n 个数字代表第一块积木每个单位的高度
第三行给出 m 个数字代表第二块积木每个单位的高度 1≤n,m≤1000
一个整数,表示拼接后的积木的最短长度
输入
7 10
2212112
2112112112
输出
10
输入
3 2
222
22
输出
5