无法用复杂状态进行转移时改变计算方式；整体考虑；压缩空间优化时间

传送门：$>here<$

题意

给出两个字符串a,b，可以将他们穿插起来（相对位置不变）。要求最小化ΣL(c)，其中L(c)的定义时在穿插完的字符串总，字符c的最大位置与最小位置的差。

数据范围：$n \leq 5000$

Solution

问题的转化

根据LCS的模型很容易想到dp(i,j)表示a的前i个与b的前j个穿插后的最小L。决策也很明显，要么将i放在最后，要么放j在最后。

如何转移呢？如果要利用这样的状态进行转移，肯定需要知道每种字符出现的最早位置。这样的话状态就变得很大了……

既然用直接的方法无法进行转移，那么必须改变计算方法！将dp(i,j)的意义改为将a的前i个与b的前j个合并后对最终答案的最优贡献。也就是说，不要将dp(i,j)作为子问题去考虑，而是考虑这一部分对整体的贡献。

将题目要求的某种字符的最大位置与最小位置的差看做一条线段，这条线段从这个字符首次出现开始延伸，直到最后一个这种字符出现。那么题目要求最小化的就是26根线段的总长度。那么dp(i,j)就是表示填完a的前i个与b的前j个以后线段的最小总长。

利用DP来解决

要计算最小总长（假设现在选择将a[i]放在最后），那么就考虑将a[i]填入后总长增加多少？很显然，对于那些还没有出现完的字符，它们对应的线段长度就要+1。什么意思？对于a[i]前面的每种字符，若还有可能在a[i]后方出现，那么对应的线段长度需要延伸。如果某种字符在a[i]之后再也不会出现了，那就不用延伸了。因此，填完a[i]后延伸的总长度就是还没有出现完的字符个数。

值得注意的是，这里的dp(i,j)既然不是子问题，那是如何保证DP的性质的呢？结合深搜来理解一下，假设最终字符的最后几位怎么填已经知道，那么前面怎么填最优？由于之前出现了哪些字符是确定的，因此最后几位在填的时候延伸的总长度是确定的，那么也就是最小化前面的总长度，那么也就是dp(i,j)了。

透过题解看本质

问题的转化

当发现当前问题极难转移时，不妨换一种计算思路。大多数时候都是这样的。既然子问题无法考虑，那就整体考虑。说白了就这两种思路。

形象生动

把位置之差理解为线段很直观便于思考。避免去空想那些太抽象的东西 。

my code

值得注意的是如果用二维DP会炸。幸好可以直接滚动数组变成1维。

还发现优化空间能够帮助优化时间。

/*By DennyQi 2019*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 10010;
const int MAXM = 20010;
const int INF = 0x3f3f3f3f;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
    int x = 0; int w = 1; register char c = getchar();
    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());
    if(c == '-') w = -1, c = getchar();
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;
}
int T,dp[5010],cnt[5010],lsta[30],lstb[30],fsta[30],fstb[30],la,lb;
char a[5010],b[5010];
inline void Init_cnt(){
    memset(lsta,0,sizeof(lsta));
    memset(lstb,0,sizeof(lstb));
    memset(fsta,0x3f,sizeof(fsta));
    memset(fstb,0x3f,sizeof(fstb));
    for(int i = 1; i <= la; ++i){
        lsta[a[i]-'A'] = max(lsta[a[i]-'A'],i);
        fsta[a[i]-'A'] = min(fsta[a[i]-'A'],i);
    }
    for(int i = 1; i <= lb; ++i){
        lstb[b[i]-'A'] = max(lstb[b[i]-'A'],i);
        fstb[b[i]-'A'] = min(fstb[b[i]-'A'],i);
    }
}
inline void DP(){
    memset(dp,INF,sizeof(dp));
    memset(cnt,0,sizeof(cnt));
    char cur;
    dp[0] = 0;
    for(int i = 0; i <= la; ++i){
        for(int j = 0; j <= lb; ++j){
            if(i==0 && j==0) continue;
            if(i == 0){    
                cnt[j] = cnt[j-1];
                cur = b[j]-'A';
                if(j == fstb[cur]) ++cnt[j];
                if(j == lstb[cur] && lsta[cur] == 0) --cnt[j];
            }
            else{
                cur = a[i]-'A';
                if(j >= lstb[cur] && i >= lsta[cur]) --cnt[j];
                if(j < fstb[cur] && i == fsta[cur]) ++cnt[j];
            }
            dp[j] = min((j==0)?INF:dp[j-1], (i==0)?INF:dp[j])+cnt[j];
        }
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s%s",a+1,b+1);
        la = strlen(a+1), lb = strlen(b+1);
        Init_cnt();
        DP();
        printf("%d\n",dp[lb]);
    }
    return 0;
}