p*****2
发帖数: 21240 | 1 有一个字符串，长度n，由k个字母组成 2<=k<=26, 都是大写字母
你可以替换任意一个字符为其他的字符，问如何以最少的次数替换，使得相邻的字母不
同。需要输出最少的次数和结果。
比如
n k
6 3
ABBACC
2
ABCACA
3 2
BBB
1
BAB | a***o
发帖数: 1182 | 2 k=2时候要处理一下?
【在 p*****2 的大作中提到】
: 有一个字符串，长度n，由k个字母组成 2<=k<=26, 都是大写字母
: 你可以替换任意一个字符为其他的字符，问如何以最少的次数替换，使得相邻的字母不
: 同。需要输出最少的次数和结果。
: 比如
: n k
: 6 3
: ABBACC
: 2
: ABCACA
: 3 2
| j*****y
发帖数: 1071 | 3 感觉 k>= 3比较好弄。 k= 2稍微还要想想。下面是 k >= 3的思路
先看 A[i], A[i + 1], A[i + 2],
case 1: A[i], A[i + 1], A[i + 2] 相同，改变 A[i + 1], 然后看
A[i + 2], A[i + 3], A[i + 4]
case 2: A[i], A[i + 1] 相同，改变 A[i], 然后看 A[i + 2], A[i + 3], A[i + 4]
case 3: A[i + 1], A[i + 2]相同, 这个时候看 A[i + 1]，A[i + 2], A[i + 3];
case 4: A[i], A[i + 1], A[i + 2]都不相同，这个时候看A[i + 2], A[i + 3], A[i
+ 4]
【在 p*****2 的大作中提到】
: 有一个字符串，长度n，由k个字母组成 2<=k<=26, 都是大写字母
: 你可以替换任意一个字符为其他的字符，问如何以最少的次数替换，使得相邻的字母不
: 同。需要输出最少的次数和结果。
: 比如
: n k
: 6 3
: ABBACC
: 2
: ABCACA
: 3 2
| a***o
发帖数: 1182 | 4 k=2也好做,就俩情况ABABABA和BABABAB
数数一下就行了
4]
[i
【在 j*****y 的大作中提到】
: 感觉 k>= 3比较好弄。 k= 2稍微还要想想。下面是 k >= 3的思路
: 先看 A[i], A[i + 1], A[i + 2],
: case 1: A[i], A[i + 1], A[i + 2] 相同，改变 A[i + 1], 然后看
: A[i + 2], A[i + 3], A[i + 4]
: case 2: A[i], A[i + 1] 相同，改变 A[i], 然后看 A[i + 2], A[i + 3], A[i + 4]
: case 3: A[i + 1], A[i + 2]相同, 这个时候看 A[i + 1]，A[i + 2], A[i + 3];
: case 4: A[i], A[i + 1], A[i + 2]都不相同，这个时候看A[i + 2], A[i + 3], A[i
: + 4]
|
|
