题解 UVA1625 【颜色的长度 Color Length】
hez_EX
·
·
题解
跟楼上一样，第一篇题解就是这么蓝的题。
大致看了一下，好像没什么题解和我的思路一样，就发一篇。
DP 四要素
状态设计
#### 转移方程
这里采用刷表法：
$$dp[i+1][j]=\min\{dp[i][j]+exi[i+1][j],dp[i+1][j]\}$$
$$dp[i][j+1]=\min\{dp[i][j]+exi[i][j+1],dp[i][j+1]\}$$
#### 初态
初始时将所有的 $dp[i][j]$ 赋一个很大的值方便转移。同时特别地有： $dp[0][0]=0$。
#### 终态
我们所求的即是 $dp[n][m]$。
### 指标函数
此题重点是指标函数的求法，在此即表示为 $exi[i][j]$，以下记第一个序列为 $A$，第二个序列为 $B$，我大致总结了一下我的做法，由上述方程不难想到整个 DP 过程就是在方格纸上求一条路径使其最终权值最小，而权值的计算这里采用**二维差分**处理。~~讨论现在来读一年前的代码的感觉。~~
先讲讲指标函数的意义：
暂时先不考虑区间开闭问题，深色是答案序列中实际存在的颜色，浅色部分是指其未配对产生的贡献，当现在的答案序列合并成这样时，如果我们再加入任意颜色，其对答案的贡献为 $4$，因为四个未配对的颜色无论如何都会增长 $1$ 的长度，而我们的 $exi[i][j]$ 数组就是用来统计**转移到**考虑 $A$ 前 $i$ 个，考虑 $B$ 前 $j$ 个时的贡献。就像这样：
紫框的是其产生的新贡献，我们只需要求出这每一步的新贡献就可以转移了。
现在根据上述方案建立转移用的“方格纸”，我们观察到颜色用字母表示，考虑每一种颜色的话枚举次数少，所以先研究某种单一颜色插入后对“方格纸”上权值的贡献，我们记一个颜色 $c$ 在 $A$ 中第一出现在下标 $sta[c]$ 最后一次出现在下标 $stb[c]$，序列 $B$ 记号同理，则我们可以发现对于颜色 $c$ 在转移时带来的贡献如下图：
这里向右走指取序列 $A$ 中的一位，向下走指取序列 $B$ 中的一位，易得在蓝色区域每转移一步就会有 $1$ 的贡献，这里我们采用前开后闭避免长度算多，不必强求像我一样，前闭后开也是可行的。
注意特殊情况：某种颜色只存在于一个序列里，这个时候我们要区间加的范围如下图：
同理于仅存于序列 $B$ 的情况。
如上文所述，这里我们需要用到区间修改，但是最终我们需要将每个点的贡献均统计出来，所以必然要求全图的前缀和，于此没必要用二维树状数组或是树套树这种~~毒瘤~~数据结构，~~我绝对不会告诉你我一上来想到的是二维树状数组，~~ 仅使用二维差分即可。
### [AC](https://www.luogu.com.cn/record/97143741) 代码如下
代码中名称与文中使用的记号**完全一样**，请放心食用。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
char a[5005],b[5005];
int n,m,t,sta[128],stb[128],ena[128],enb[128],dif[5005][5005],sum[5005][5005],exi[5005][5005],dp[5005][5005];
int main()
{
cin>>t;
while(t--)
{
cin>>(a+1)>>(b+1);n=strlen(a+1);m=strlen(b+1);
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++) dif[i][j]=sum[i][j]=exi[i][j]=0,dp[i][j]=inf;
}
//统计各颜色在序列中出现的位置
for(int i=0;i<128;i++) sta[i]=stb[i]=inf,ena[i]=enb[i]=0;
for(int i=1;i<=n;i++) if(sta[a[i]]==inf) sta[a[i]]=i;
for(int i=1;i<=m;i++) if(stb[b[i]]==inf) stb[b[i]]=i;
for(int i=n;i>=1;i--) if(ena[a[i]]==0) ena[a[i]]=i;
for(int i=m;i>=1;i--) if(enb[b[i]]==0) enb[b[i]]=i;
for(int i=0;i<128;i++)
{
if(sta[i]<inf&&stb[i]<inf) //改颜色同时出现在两个序列中
{
dif[0][stb[i]]++;dif[ena[i]][stb[i]]--;
dif[sta[i]][0]++;dif[sta[i]][enb[i]]--;
dif[sta[i]][stb[i]]--;dif[ena[i]][stb[i]]++;dif[sta[i]][enb[i]]++;dif[ena[i]][enb[i]]--;
}
//仅出现在一个序列中
else if(sta[i]<inf&&sta[i]<ena[i]) dif[sta[i]][0]++,dif[ena[i]][0]--;
else if(stb[i]<inf&&stb[i]<enb[i]) dif[0][stb[i]]++,dif[0][enb[i]]--;
}
//前缀和求“方格纸”（我也不知道为什么循环两遍了，可能是当时脑抽吧QAQ）
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(j==0) sum[i][j]=dif[i][j];
else sum[i][j]=sum[i][j-1]+dif[i][j];
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(i==0) exi[i][j]=sum[i][j];
else exi[i][j]=exi[i-1][j]+sum[i][j];
dp[0][0]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
dp[i+1][j]=min(dp[i+1][j],dp[i][j]+exi[i+1][j]);
dp[i][j+1]=min(dp[i][j+1],dp[i][j]+exi[i][j+1]);
}
cout<<dp[n][m]<<endl;
}
return 0;
}
```