Uva1625 -Color Length（DP）

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