求助谷民 这段程序是什么意思
  • 板块灌水区
  • 楼主LAICZ
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/8/2 11:04
  • 上次更新2023/11/3 06:24:28
查看原帖
求助谷民 这段程序是什么意思
606173
LAICZ楼主2023/8/2 11:04

好久以前写的,注释爆炸了,想问一下这段程序的意思。

#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;
}


2023/8/2 11:04
加载中...