dp[i][j]可以这样构造，s1的前i个和s2的前j个字符构成的序列对答案的最小贡献，更新时只需要知道s1[1:i]和s2[1:j]哪种颜色已经开始但还未结束
对无后效性有了新的理解：利用已知信息更新未知信息
#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N = 5000 + 5;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
const int mod = 998244353;
ll fast_pow(ll a,ll b){
ll ans = 1;
while(b){
if(b&1)ans = (ans * a)%mod;
a = (a * a)%mod;
b>>=1;
}
return (ans%mod);
}
typedef pair<int,int> pii;
char s1[N],s2[N];
ll dp[N][N];
int lowa[30],lowb[30],higha[30],highb[30],n,m;
void make(){
for(int i = 1;i <= n;i++)higha[s1[i] - 'A'] = i;
for(int i = 1;i <= m;i++)highb[s2[i] - 'A'] = i;
for(int i = n;i >= 1;i--)lowa[s1[i] - 'A'] = i;
for(int i = m;i >= 1;i--)lowb[s2[i] - 'A'] = i;
//for(int i = 0;i < 26;i++)
// cout<<char('A' + i)<<lowb[i]<<" "<<highb[i]<<endl;
}
int get(int a,int b){
int ans = 0;
for(int i = 0;i < 26;i++){
if( (lowa[i] != -1 && lowa[i] <= a || lowb[i] != -1 && lowb[i] <= b) && (higha[i] > a || highb[i]> b))ans++;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#if DBG
freopen("input.txt","r",stdin);
#endif
int T;
cin>>T;
while(T--){
cin>>(s1 + 1);
cin>>(s2 + 1);
n = strlen(s1 + 1);
m = strlen(s2 + 1);
for(int i = 0;i <= n;i++)
for(int j = 0;j <= m;j++)dp[i][j] = INF;
dp[0][0] = 0;
for(int i = 0;i < 26;i++)lowa[i] = lowb[i] = higha[i] = highb[i] = -1;
make();
for(int i = 0;i <= n;i++){
for(int j = 0;j <= m;j++){
if(i > 0)dp[i][j] = min(dp[i - 1][j] + get(i - 1,j),dp[i][j]);
if(j > 0)dp[i][j] = min(dp[i][j - 1] + get(i,j - 1),dp[i][j]);
//cout<<dp[i][j]<<" ";
}
//cout<<endl;
}
cout<<dp[n][m]<<endl;
}
return 0;
}
本文地址：https://blog.csdn.net/qq_20252251/article/details/109367692
