好久以前写的,注释爆炸了,想问一下这段程序的意思。
#include <bits/stdc++.h>
#include <math.h>
#include <algorithm>
using namespace std;
int dp[5050][5050],plan[5050][5050],lena,lenb;
//dp(i,j)±íʾs1µÄǰiλÓës2µÄǰjλµÄ×î¶Ì¸¸ÐòÁ㤶È
//plan(i,j)±íʾs1µÄǰiλÓës2µÄǰjλÓжàÉÙÖÖ²»Í¬µÄ×î¶Ì¸¸ÐòÁÐ
char a[5050],b[5050];
int main(){
scanf("%s",&a);
scanf("%s",&b);
lena = strlen(a);
lenb = strlen(b);
for(int i = lena;i > 0;i--){
a[i] = a[i - 1];
}
for(int i = lenb;i > 0;i--){
b[i] = b[i - 1];
}
for(int i = 0;i <= max(lena,lenb);i++){
dp[i][0] = dp[0][i] = i;
//ÏÔ¶øÒ×¼û,s1/s2µÄǰiλÓës2/s1µÄǰ0λ×î¶Ì¸¸ÐòÁ㤶ÈÏÔÈ»ÊÇs1/s2µÄ³¤¶È
plan[i][0] = plan[0][i] = 1;
//ÏÔ¶øÒ×¼û,s1/s2µÄǰiλÓës2/s1µÄǰ0λµÄ²»Í¬×î¶Ì¸¸ÐòÁÐÖÖÊýÏÔÈ»ÊÇ1,·½°¸Îªs1/s2
}
for(int i = 1;i <= lena;i++){
for(int j = 1;j <= lenb;j++){
if(a[i] == b[j]){
dp[i][j] = dp[i - 1][j - 1] + 1;
plan[i][j] += plan[i - 1][j - 1];
}else{
dp[i][j] = min(dp[i - 1][j],dp[i][j - 1]) + 1;
if(dp[i][j] == dp[i - 1][j] + 1 && a[i] != b[j]){
plan[i][j] += plan[i - 1][j];
//´Ódp(i-1,j)×ªÒÆ
}
if(dp[i][j] == dp[i][j - 1] + 1 && a[i] != b[j]){
plan[i][j] += plan[i][j - 1];
//´Ódp(i,j-1)×ªÒÆ
}
}
if(a[i] != b[j] && dp[i][j] == dp[i - 1][j - 1]){
plan[i][j] -= plan[i - 1][j - 1];
//dp(i-1,j)Óëdp(i,j-1)¾ù´Ódp(i-1,j-1)×ªÒÆ,¾ÍÖØ¸´ÁË,¼õÈ¥¶à¼ÓµÄplan(i-1,j-1)
}
plan[i][j] %= 2019;//²½²½È¡Ä£
}
}
printf("%d %d",dp[lena][lenb],plan[lena][lenb]);
return 0;
}