lboj 8287: 【暑假作业第一套#1T4】加倍快乐
做题随笔/题解
文章目录
- lboj 8287: 【暑假作业第一套#1T4】加倍快乐
- 做题随笔/题解
-
- 题意简述
- 赛时想法
- 正解
-
- 🎭天人大战
- 📒梳理一下
-
- 考虑DP转移方程式
- 初始化
- 最终答案
- 优化
- 复杂度分析
- 🗝️参考代码
- 🏁总结回顾
- 🩸易错点与调试心得（血泪汇总）
-
- 1. ⚠️ 无解判定：不是 `> len/2`，而是 `> (len+1)/2`（鸽巢原理）
- 2. ⚠️ DP转移时 `p` 的语义（最隐蔽的位置偏移）
- 3. ⚠️ 最后答案一定要除以 2
- 4. ⚠️ 数组维度定义顺序（`pos[3][N]` 与 `pos[N][3]`）
- 5. ⚠️ `fg` 标志的检测与空串情况
- 6. ⚠️ `memset` 的赋值要足够大
题意简述
给我们一个长度小于等于400且仅包含 A 、C、 K 三种字符的字符串S(后续讲解中令：len=S.length(),将S存到b[1~len]中)。现有一种操作及每次操作交换两个相邻的字母，要求对S做尽可能少的操作使得S中不出现相邻的 AA 、CC、 KK 即可。（若不可能满足要求，则输出 Impossible! ）
赛时想法
嗳，刚复习完区间DP计数这不就来了吗，400的数据范围一看就知道是留给dp[l][r]和两重循环的呗,她甚至留了一个O(n^3)给我！简单推一下这题随便切！
不对！w(ﾟДﾟ)w 有问题：
1、子串内字母全部不确定（而且还是交换），我怎么知道dp[l][r]里局部最优解把那些字母换到哪儿去了；
2、而且说到局部最优解我就来气，如何保证局部最优能推广到全局？；
3、 DP要有初始状态和转移公式： 初始状态可以用遍历原S将合法子串标记为0，其它是极大值—— 但转移公式总不能蒙混过关了吧？可我推不出来啊，对于这个数据结构所谓特殊的情况太多了，嘶…
好吧到这里其实已经可以将区间计数DP排除了，以至于后来A了之后还想试试看能不能攻克都碰壁了。
但是随后，“哎呀DP⚠️不行，这题估计是贪心吧（严肃打草稿+敲代码）…”。
🛺事实证明 J组 难度的T4被我严重低估了。（谁家好人T4还考贪心啊喂）
咳咳，好吧最后样例没过。
毕竟 J组 T4考区间计数DP还是比较少吧？
OK现在让我们看一下——
正解
没错这题就是DP，不过我们可以思路打开 (交叉步摊手):
事实上，这道题有一个关键性质：相邻交换不会改变同种字符的相对顺序1。 因此，我们可以把原串中的 A、C、K 分别看作三个有序队列（A₁, A₂, …；C₁, C₂, …；K₁, K₂, …）。 最终排成的合法字符串，其实就是这三个队列按某种顺序交错合并（Interleaving）的结果。 这种 DP 被称为 多路归并 DP（Multi‑way Merge DP），它的状态天然就是“从每路队列中取了多少个元素”。
如果这题是多路归并DP： Why？
🎭天人大战
- 反方小人：朴素DP要满足无后效性，你自己之前也说了这道题既没有确定局部状态（信息不充分），决策区间时也没有单向性（因为就算用1≤i<j≤len,拿dp[i]去推dp[j]也讨论不全），无法构造DAG。那如何能说DP呢？
- 正方小人：那我就不只用下标来定义 DP 数组，而是把原串看成三路队列——A、C、K 各成一队，取数时按原顺序取。状态就定义为从三路队列中各取了多少个前缀，这样信息就完整了！
- 反方小人：朴素DP在递推计算DP数组时要利用转移方程来快速计算每一项，你连转移方程式能否适用所有特殊情况都不确定。
- 正方小人：那我就再升维，既然我要用朴素DP从1~len遍历，在前i个元素合法情况下对dp[i+1]的扩展只考虑b[i+1]与b[i]即可，所以升的这一维就存结尾元素是啥。而后在统计操作次数时，我就找在b[i]之后第一个要求找的元素下标一减。（还没完，具体操作次数要除二，后面解释）
基于上面的队列模型，我们的状态设计就水到渠成了：
📒梳理一下
我们决定使用朴素DP求解，需要数组：dp[i][a][c][k][lst],表示使从b[1]~b[i]的元素全部合法且包含a个'A'、c个'C'、k个'K'，并以lst∈{0,1,2}为结尾的最小操作数。(0=‘A’ , 1=‘C’ , 2=‘K’)
考虑DP转移方程式
我们可以用“向前转移”（由已知状态推出未知状态）的方式写出：
假设当前状态为 (i, a, c, k, lst)，且 i < len（总长度）。 接下来我们要在第 i+1 个位置放入一个字符 ch（ch ∈ {0,1,2}），必须满足：
当放入 ch 时，新的状态为：
- i' = i + 1
- 对应字符计数加 1：a' = a + (ch==0 ? 1 : 0)，c' = c + (ch==1 ? 1 : 0)，k' = k + (ch==2 ? 1 : 0)
- 新的末尾 lst' = ch
转移代价：第 i+1 个位置是 原串中第 cnt+1 个 ch 字符（因为已经用了 cnt 个该字符，下一个就是第 cnt+1 个），其原始位置为 pos[ch][cnt+1]（1‑based）。 因此它需要移动的步数为 |(i+1) – pos[ch][cnt+1]|。
于是，向前转移的方程为（设当前状态为 (i, a, c, k, lst)，准备放入字符 ch）：
dp
[
i
+
1
]
[
a
′
]
[
c
′
]
[
k
′
]
[
c
h
]
=
min
(
dp
[
i
+
1
]
[
a
′
]
[
c
′
]
[
k
′
]
[
c
h
]
,
dp
[
i
]
[
a
]
[
c
]
[
k
]
[
l
s
t
]
+
∣
(
i
+
1
)
−
pos
[
c
h
]
[
c
n
t
+
1
]
∣
)
\\text{dp}[i+1][a'][c'][k'][ch] = \\min\\left( \\text{dp}[i+1][a'][c'][k'][ch], \\text{dp}[i][a][c][k][lst] + \\left| (i+1) – \\text{pos}[ch][cnt+1] \\right| \\right)
dp[i+1][a′][c′][k′][ch]=min(dp[i+1][a′][c′][k′][ch],dp[i][a][c][k][lst]+∣(i+1)−pos[ch][cnt+1]∣)
其中：
- ( a’ = a + [ch=0] )，( c’ = c + [ch=1] )，( k’ = k + [ch=2] )
- ( cnt ) 是当前已使用的 ch 字符数量（例如若 ch=0，则 ( cnt = a )）
- pos[ch][cnt+1] 是原串中第 ( cnt+1 ) 个 ch 的位置（1‑based）
初始化
一个字符都没放时（i=0, a=c=k=0），末尾字符视为“空”，此时可以放入任意字符。因此我们将所有 lst 的初始值都设为 0：
d
p
[
0
]
[
0
]
[
0
]
[
0
]
[
0
]
=
d
p
[
0
]
[
0
]
[
0
]
[
0
]
[
1
]
=
d
p
[
0
]
[
0
]
[
0
]
[
0
]
[
2
]
=
0
dp[0][0][0][0][0]=dp[0][0][0][0][1]=dp[0][0][0][0][2]=0
dp[0][0][0][0][0]=dp[0][0][0][0][1]=dp[0][0][0][0][2]=0 其余所有状态初始化为 INF（极大值）。
最终答案
当填满所有 len 个位置时，i = len，并且 a = totA，c = totC，k = totK。 此时取三种末尾字符的最小距离和：
a
n
s
d
=
m
i
n
(
d
p
[
l
e
n
]
[
t
o
t
A
]
[
t
o
t
C
]
[
t
o
t
K
]
[
l
s
t
]
)
ans_d=min (dp[len][tot_A][tot_C][tot_K][lst])
ansd=min (dp[len][totA][totC][totK][lst]) 实际最少相邻交换次数为：
a
n
s
=
a
n
s
d
/
2
ans=ans_d/2
ans=ansd/2
优化
即使len<=400,五维的dp还是要爆滴，不过很容易想到i=a+c+k,所以将i这一维优化掉就剩下dp[a][c][k][lst],除去lst这个常数，三维妥妥哒2。o(〃＾▽＾〃)o
压缩后，状态变为 dp[i][j][k][lst]（i,j,k 分别表示已取的 A、C、K 数量），转移方程采用向后拉取（即由前驱状态推当前状态）写法，与代码一致：
d
p
[
i
]
[
j
]
[
k
]
[
0
]
=
min
(
d
p
[
i
−
1
]
[
j
]
[
k
]
[
1
]
,
d
p
[
i
−
1
]
[
j
]
[
k
]
[
2
]
)
+
∣
(
i
+
j
+
k
)
−
p
o
s
[
0
]
[
i
]
∣
,
i
>
0
d
p
[
i
]
[
j
]
[
k
]
[
1
]
=
min
(
d
p
[
i
]
[
j
−
1
]
[
k
]
[
0
]
,
d
p
[
i
]
[
j
−
1
]
[
k
]
[
2
]
)
+
∣
(
i
+
j
+
k
)
−
p
o
s
[
1
]
[
j
]
∣
,
j
>
0
d
p
[
i
]
[
j
]
[
k
]
[
2
]
=
min
(
d
p
[
i
]
[
j
]
[
k
−
1
]
[
0
]
,
d
p
[
i
]
[
j
]
[
k
−
1
]
[
1
]
)
+
∣
(
i
+
j
+
k
)
−
p
o
s
[
2
]
[
k
]
∣
,
k
>
0
\\begin{aligned} dp[i][j][k][0] &= \\min(dp[i-1][j][k][1],\\; dp[i-1][j][k][2]) + \\left| (i+j+k) – pos[0][i] \\right|, \\quad i>0 \\\\ dp[i][j][k][1] &= \\min(dp[i][j-1][k][0],\\; dp[i][j-1][k][2]) + \\left| (i+j+k) – pos[1][j] \\right|, \\quad j>0 \\\\ dp[i][j][k][2] &= \\min(dp[i][j][k-1][0],\\; dp[i][j][k-1][1]) + \\left| (i+j+k) – pos[2][k] \\right|, \\quad k>0 \\end{aligned}
dp[i][j][k][0]dp[i][j][k][1]dp[i][j][k][2]=min(dp[i−1][j][k][1],dp[i−1][j][k][2])+∣(i+j+k)−pos[0][i]∣,i>0=min(dp[i][j−1][k][0],dp[i][j−1][k][2])+∣(i+j+k)−pos[1][j]∣,j>0=min(dp[i][j][k−1][0],dp[i][j][k−1][1])+∣(i+j+k)−pos[2][k]∣,k>0
注意这里 p = i+j+k 表示当前正在放置的位置（1‑based），所以直接与 pos 相减。
复杂度分析
-
时间复杂度：三重循环 O(cnt_A * cnt_C * cnt_K)，最坏情况约为 134^3 ≈ 2.4×10^6 次转移，完全可过。
-
空间复杂度：O(cnt_A * cnt_C * cnt_K * 3)，约 80 MB（使用 int 时），在 512 MB 限制内安全。
终于到了大家喜闻乐见的——
🗝️参考代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int o=1e5+22;
int num[3]={0}; // 各字符总数
unordered_map<char,int> f; // 字符→编号
string s;
int a[405]={0}; // 原串编号，1-based
int pos[3][402]={0}; // pos[ch][cnt] = 第cnt个ch在原串的位置
int dp[222][222][222][3]={0}; // dp[i][j][k][last]
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>s;
int fg=0, len=s.length();
f['A']=0; f['C']=1; f['K']=2;
for(int i=0;i<len;i++) a[i+1]=f[s[i]];
// 统计 + 记录位置 + 无解判断 + 检测原串是否已合法
for(int i=1;i<=len;i++)
{
if(a[i]==a[i+1] && i!=len) fg=1;
num[a[i]]++;
if(num[a[i]] > (len+1)/2) { cout<<"Impossible!\\n"; return 0; }
pos[a[i]][num[a[i]]] = i;
}
if(!fg) { cout<<"0\\n"; return 0; }
// DP 初始化
memset(dp,0x3f3f3f,sizeof(dp));
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
for(int i=0;i<=num[0];i++)
for(int j=0;j<=num[1];j++)
for(int k=0;k<=num[2];k++)
{
int p = i+j+k; // 当前正要放置的位置（1‑based），等于已填字符总数
if(i) dp[i][j][k][0] = min(dp[i–1][j][k][1], dp[i–1][j][k][2]) + abs(p – pos[0][i]);
if(j) dp[i][j][k][1] = min(dp[i][j–1][k][0], dp[i][j–1][k][2]) + abs(p – pos[1][j]);
if(k) dp[i][j][k][2] = min(dp[i][j][k–1][0], dp[i][j][k–1][1]) + abs(p – pos[2][k]);
}
int ans = min({dp[num[0]][num[1]][num[2]][0],
dp[num[0]][num[1]][num[2]][1],
dp[num[0]][num[1]][num[2]][2]});
cout << ans/2 << "\\n"; // 距离和 = 交换次数 × 2
return 0;
}
🏁总结回顾
总的来说这道题还算一道比较好的多路归并 DP,关键在于识别出“同种字符相对顺序不变”，从而将原问题转化为三路有序队列的交错排列问题：
- 我们把原串中所有的 A 排成一个序列，所有的 C 排成一个序列，所有的 K 排成一个序列。原串其实是由这三路序列“交错合并”而成的。
- dp[i][j][k] 就表示：从 A 序列里取了前 i 个，从 C 序列里取了前 j 个，从 K 序列里取了前 k 个。
- 状态转移，本质上就是决定下一步从哪一路序列“取队头”。这和归并排序中合并多个有序数组的思维完全一致。
🩸易错点与调试心得（血泪汇总）
1. ⚠️ 无解判定：不是 > len/2，而是 > (len+1)/2（鸽巢原理）
- 错误写法：if (num > len / 2) Impossible!
- 正确写法：if (num > (len + 1) / 2) Impossible!
- 原因：长度为 len 的序列，要保证没有相邻相同，某个字符最多能出现 (len+1)/2 次（向上取整）。 例如 len=5，最多能放 3 个 A（A _ A _ A），此时 5/2=2 会误判为无解。
2. ⚠️ DP转移时 p 的语义（最隐蔽的位置偏移）
- 错误写法：int p = i + j + k + 1; （误以为需要加1）
- 正确写法：int p = i + j + k;
- 原因：在压缩后的 DP 中，dp[i][j][k][lst] 表示已经使用了 i 个 A、j 个 C、k 个 K，即已填字符总数为 i+j+k。 由于位置从 1 开始编号，当前正要填的这个位置的编号就是 i+j+k（因为前 i+j+k 个位置已经被占满）。 因此，转移时直接令 p = i+j+k，代价为 abs(p – pos[ch][cnt])，无需再加 1。
3. ⚠️ 最后答案一定要除以 2
- 很多人 DP 算出 ans 后直接输出，结果比答案大一倍。
- 原因：一次相邻交换（如 AC → CA），A 向右走了一步，C 向左走了一步。DP 累加的是所有字符移动步数的总和，而一次交换贡献了 2 步，所以实际交换次数 = ans / 2。
4. ⚠️ 数组维度定义顺序（pos[3][N] 与 pos[N][3]）
- 错误写法：int pos[405][3]; 赋值时写 pos[a[i]][num] = i;，读取时写 pos[0][i]。
- 这会导致赋值时把数据写在 [字符编号][出现次数]，但读取时却当成 [出现次数][字符编号]，两者完全错位，取到的永远是 0（未初始化）。
- 正确写法：必须定义为 int pos[3][405];，第一维是字符种类（0~2），第二维是出现次数。赋值和读取保持一致。
5. ⚠️ fg 标志的检测与空串情况
- 如果原串已经是合法的（fg == 0），记得直接输出 0 并 return。
- 易错点：如果忘记特判，直接跑 DP，虽然也有可能算出 0，但如果无解检查通过且 dp 初始化没问题，输出也是 0。但特判可以避免后续 dp 数组未更新时访问到极大值的风险，且减少不必要的计算。
6. ⚠️ memset 的赋值要足够大
- 因为 dp 里存的是距离和，最大也就 400*400/2 ≈ 80000，但要设置为 无穷大。
- 推荐 memset(dp, 0x3f, sizeof(dp));，这样每个 int 变成 0x3f3f3f3f（约 1e9），远超最大代价，相加也不会溢出。
思路已清，代码已毕。 若有疑问，或发现文中遗漏的坑点，欢迎留言指出，我会及时更新。
—————— 以上。
也就是同种字符在交换前后的相对位置关系始终不变，比如第2个’A’永远不会跑到第1个’A’的前面，因为两个相同字符交换不会改变字符串，所以它们在交换过程中不可能互相跨越，相对顺序自然保持 ↩︎
这也是“多路归并 DP”的典型特征：维数 = 队列数，状态值 = 取到各队列的前缀。 ↩︎
