1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic #include #include //do setprecision #include #include #include "message.h" using namespace std; #define FOR(i,b,e) for(int i=(b);i<(e);++i) #define FORQ(i,b,e) for(int i=(b);i<=(e);++i) #define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i) #define REP(x, n) for(int x = 0; x < (n); ++x) #define ST first #define ND second #define PB push_back #define MP make_pair #define LL long long #define ULL unsigned LL #define LD long double const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342; #define MR 100010 pair **dp; char a[MR], b[MR]; int main() { if(!MyNodeId()) { int n, m; scanf("%d%d%s%s", &n, &m, a, b); dp = new pair*[n+1]; FORQ(i,0,n) dp[i] = new pair[m+1]; dp[0][0] = MP(0,0); REP(i,n) dp[i+1][0] = MP(i+1,0); REP(j,m) dp[0][j+1] = MP(j+1,0); FORQ(i,1,n)FORQ(j,1,m) { dp[i][j] = min(dp[i-1][j], dp[i][j-1]); dp[i][j].ST++; if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min(dp[i][j],MP(dp[i-1][j-1].ST+1,dp[i-1][j-1].ND+(b[j-1]>a[i-1]))); } printf("%d %d\n", dp[n][m].ST, dp[n][m].ND); } return 0; }