【BOI2013】文本编辑器——全面理解线头DP

【BOI2013】文本编辑器 (Standard IO) Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits

Description Input

第一行包含了整数N，表示该文档的长度。下一行包含N个字符，每一个都是十个小写字母“a”到“j”之一。输入的第一个和最后一个字母都不是“e”。

Output

输出一个整数，表示Victor需要删除所有的“e”最少的按键次数。

Sample Input

35

chefeddiefedjeffeachbigagedegghehad

Sample Output

36

解释：其中一个最优方案是：fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx

Data Constraint

50%数据：N ≤ 500

另外10%的数据：N ≤ 5000

100%的数据：N ≤ 70 000

题目大意

本题可以转化为，求一种路线进行方案。每一次可以从一个点向后跳到另一个点，然后从这个点往回走到一个点（也可以不走）之后再跳到下一个点。每一次的跳跃与行进都有特定的代价。求经过所有必经点的最小代价和。 很容易想到，每一次往前走都不能到上一次飞跃的落脚点以前。也就是 这样跳一定不是最优的。如果你能理解这个，就可以继续向下看了

算法介绍

线头DP 就是像滚线团一样，最终的形态为：

这个就是线头DP的大致状态（DP的转移路线） 我们要做的，不是像正常的DP一样去模拟这些路线，而是要通过像是穿针引线一样的将这些路径组合起来。 我们可以形象的理解为每一次飞跃都是一条飞线，而每一个向前走的路径都是一段粗线，粗线两端由线头组成。而且所有的线都是相连的！ 飞一条线的代价为2，而引出一条长为1的粗选代价为1！ 我们通过飞线与线头的同时移动来达到像上图一样的路径。从而得到最优解。

具体DP

观察发现，对于每一个点i与i+1.其中被线覆盖（飞线或粗线）的次数一定为1或3. 于是我们 设$f[i][j]$表示i与i+1两个点直接有且只有被覆盖了1次（飞线覆盖），飞线到达的右端点的字母j（s[k]==j) 的最小代价 设$g[i][j][k]$表示i与i+1两个点有且只有被覆盖了3次（飞线与粗线同时覆盖）,飞线到达的右端点的字母为j（s[p]==j)且粗线的右端点引出的飞线的右端点的字母为k（s[q]==k) 的最小代价。 注意！这两个状态中的线不一定是全部相连的！！也就是转移过程中求出来的答案不是正确的答案，这点很重要！！ 也就是说，只要是被覆盖的次数满足条件，就可以计入方程，其他的全部不用考虑！！（这就是线头DP最迷的地方） 然后就是DP的转移式子了。 一共由10条转移，我们逐条来解释 1、$f[i][j]=min(f[i][j],f[i-1,j](j̸=s[i]且i点不是必须点))$ 如果i-1 与 i 被一条飞线越过，这说明这条飞线很有可能也跨过了i与i+1。所以直接转移就可以。 2、$f[i][j]=min(f[i][j],f[i-1,s[i]]+2)$ 如果越过i-1与i的飞线恰好停在了i这个点，为了使得i与i+1被跨过一次，我们可以再飞出一条线，使得重新满足状态$f[i][j]$ 的定义。 3、$f[i][j]=min(f[i][j],g[i-1,s[i],j](j̸=s[i]))$ 上面两条状态都比较容易理解，这条就有点困难了。这里的$g[i-1][s[i]][j]$表示的是： 可以观察到，这里i与i+1刚好被经过了1次，所以满足f的定义。 注意：$g[i-1][s[i]][j]$ 中的状态一定i与i-1的连边的代价一定是已经计算过的。 （思考，i-1往前的边的代价是否都已经计算过了呢？） 4、$f[i][j]=min(f[i][j],g[i-1,s[i],s[i]]+2)$ 这里的情况就与第2种比较相像了。可以直接类比思考。由于篇幅有限，这里就不做阐述。 5、$g[i][j]=min(g[i][j],f[i-1,j]+3(j̸=s[i]))$ 这一条转移看上去也很诡异。为什么是正确的呢？ 这条语句也极其重要：因为它代表着新建线头！ 我们思考$f[i-1][j]$ 所表示的具体含义： 然后我们给这个图加一个线头：变成这样： 这里所需的代价为1. 然后为了保证i与i+1被覆盖3次，我们再将i与k（s[k]==j）相连： 这里，红色的边表示新加入的边。 这样就满足了g的定义。 6、$g[i][j]=min(g[i][j],f[i-1,s[i]]+5)$ 这里的转移与第2与第5个转移比较相像，就不过多阐述。 7、$g[i][j]=min(g[i][j],g[i-1,j,k]+1(j̸=s[i]且k̸=s[i]))$ 重点之三：延长线头！ $g[i-1][j][k]+1$ 表示 红色的线表示增加的代价。 满足g的定义。 8、$g[i][j]=min(g[i][j],g[i-1,s[i],k]+3(k̸=s[i]))$ 9、$g[i][j]=min(g[i][j],g[i-1,j,s[i]]+3(j̸=s[i]))$ 10、$g[i][j]=min(g[i][j],g[i-1,s[i],s[i]]+5)$ 以上三种都是对第7种情况的拓展，拓展方式与第二个十分相像。就不过多阐述了。

正确性

DP的正确性如何保证呢？ 我们发现线头DP中的链接情况总是十分混乱，这使得我们很难去分析它的正确性。 但是，我们发现这里有一个延长线头的操作。对于每一次新建完线头之后，由于不断的g数组本身的dp的积累，每一次对g数组的转移都意味着将线头向右进行延伸。由于所有的i都会参与到g数组的转移，所以所有的线头最终都会与飞线链接起来。就是说，所有的g中，$g[i-1][j][k]$中，i-1到往前所到的点的代价一定都是计算过的。这也意味着当i移动到第n个的时候，所有的线头都一定是链接的代价都一定是计算过的。于是线头DP就没有了。

实现细节

引用一下YYT的题解 1、初始化f[0,s[1]]=0; 2、假设我们的字符集a_j编号为09，那么我们将10视为一个没出现过的字符 最后dp出的ans就是f[n,10]-2 因为10不存在，所以可以把f[n,10]视作将绳子拉向一个无限远的点 又因为这样代价为2，而实际上我们并不需要这样做，所以减去2 3、当一个点是e，而我们是不需要管它的（因为要删）。 为了方便起见，我们就将这个点的f和g赋值为上一个点的(memcpy)

代码

#include<cstdio> #include<cstring> #define maxn 70001 #define N 11 int f[maxn][N],g[maxn][N][N],must[maxn]; int js=0,n; char s[maxn]; int min(int x,int y) { if (x<y) return x; return y; } int main() { int i,j,k,d; scanf("%d\n",&n); scanf("%s",s+1); memset(must,false,sizeof(must)); int ans=0; for(i=1;i<=n;i++) { if (s[i]=='e') ans+=2; if (s[i-1]=='e') must[i]=true; } memset(f,20,sizeof(f)); memset(g,20,sizeof(g)); f[0][s[1]-'a']=0; for (int i=1;i<=n;i++) { if (s[i]=='e') { memcpy(f[i],f[i-1],sizeof(f[i])); memcpy(g[i],g[i-1],sizeof(g[i])); } else { for (char j1='a';j1<='k';j1++) { int j=j1-'a'; f[i][j]=1e9; if((j1!=s[i])&&(!must[i])) f[i][j]=min(f[i][j],f[i-1][j]); f[i][j]=min(f[i][j],f[i-1][s[i]-'a']+2); if(j1!=s[i]) f[i][j]=min(f[i][j],g[i-1][s[i]-'a'][j]); f[i][j]=min(f[i][j],g[i-1][s[i]-'a'][s[i]-'a']+2); for (char k1='a';k1<='k';k1++) { int k=k1-'a'; g[i][j][k]=1e9; if(j1!=s[i]) g[i][j][k]=min(g[i][j][k],f[i-1][j]+3); g[i][j][k]=min(g[i][j][k],f[i-1][s[i]-'a']+5); if(j1!=s[i]&&k1!=s[i]) g[i][j][k]=min(g[i][j][k],g[i-1][j][k]+1); if(j1!=s[i]) g[i][j][k]=min(g[i][j][k],g[i-1][j][s[i]-'a']+3); if(k1!=s[i]) g[i][j][k]=min(g[i][j][k],g[i-1][s[i]-'a'][k]+3); g[i][j][k]=min(g[i][j][k],g[i-1][s[i]-'a'][s[i]-'a']+5); } } } } printf("%d",f[n]['k'-'a']+ans-2); return 0; }