fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll; 
  4. ll dp[1005][1005];
  5.  
  6.  
  7. int main(){
  8. 	string s,t;
  9. 	cin>>s>>t; 
  10. 	ll n = s.size();
  11. 	ll m = t.size();
  12.  
  13. 	for(ll i=0;i<=n+2;i++){
  14. 		for(ll j=0;j<=m+2;j++){
  15. 			dp[i][j] = 1e18 ; 
  16. 		}
  17. 	}
  18.  
  19. 	vector<vector<ll>> ps(n + 5, vector<ll>(30 + 1, 0)); 
  20. 	vector<vector<ll>> pt(m + 5, vector<ll>(30 + 1, 0)); 
  21.  
  22. 	for(ll i=0;i<=n-1;i++){
  23. 	    ll c = s[i]-'a';
  24. 	    c++;
  25. 	    ps[i+1][c] = 1;
  26. 	}
  27.  
  28. 	for(ll j=0;j<=m-1;j++){
  29. 	    ll c = t[j]-'a';
  30. 	    c++;
  31. 	    pt[j+1][c] = 1;
  32. 	}
  33.  
  34. 	for(ll i=1;i<=n;i++){
  35. 	    for(ll j=1;j<=28;j++){
  36. 	        ps[i][j] = ps[i][j] + ps[i-1][j];
  37. 	    }
  38. 	}
  39.  
  40. 	for(ll i=1;i<=m;i++){
  41. 	    for(ll j=1;j<=28;j++){
  42. 	        pt[i][j] = pt[i][j] + pt[i-1][j];
  43. 	    }
  44. 	}
  45.  
  46.  
  47.  
  48.  
  49. 	dp[0][0] = 0 ; 
  50.  
  51. 	for(ll i=0;i<s.size();i++){
  52. 		char c = s[i];ll g = 0;
  53. 			for(ll u=0;u<=i-1;u++){
  54. 				if(s[u]>c){
  55. 					g++;
  56. 				}
  57. 			}
  58. 		dp[i+1][0] = dp[i][0] + g;	//cout<<g<<"\n";
  59. 		}
  60.  
  61. 	for(ll j=0;j<t.size();j++){
  62. 		char c = t[j];ll g = 0;
  63. 			for(ll u=0;u<=j-1;u++){
  64. 				if(t[u]>c){
  65. 					g++;
  66. 				}
  67. 			}
  68. 		dp[0][j+1] = dp[0][j] + g;	//cout<<g<<"\n";
  69. 		}	
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76. 	for(ll i=0;i<s.size();i++){
  77. 		for(ll j=0;j<t.size();j++){
  78. 			//dp[i+1][j+1]-->dp[i][j+1].....
  79. 			//[0.....i-1]+[0......j]
  80. 			char c = s[i];ll g = 0;
  81. 			for(ll u=0;u<=i-1;u++){
  82. 				if(s[u]>c){
  83. 					g++;
  84. 				}
  85. 			}
  86. 			for(ll u=0;u<=j;u++){
  87. 				if(t[u]>c){
  88. 					g++;
  89. 				}
  90. 			}
  91.  
  92. 			dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j+1] + g); 
  93.  
  94. 			//dp[i+1][j+1]-->dp[i+1][j]....
  95. 			//[0..........i]+[0.....j-1]......
  96.  
  97. 			c = t[j];g = 0;
  98. 			for(ll u=0;u<=i;u++){
  99. 				if(s[u]>c){
  100. 					g++;
  101. 				}
  102. 			}
  103. 			for(ll u=0;u<=j-1;u++){
  104. 				if(t[u]>c){
  105. 					g++;
  106. 				}
  107. 			}
  108.  
  109. 			dp[i+1][j+1] = min(dp[i+1][j+1],dp[i+1][j] + g);
  110. 			//cout<<i+1<<" "<<j+1<<" "<<dp[i+1][j+1]<<"\n";
  111.  
  112.  
  113. 		}
  114. 	}
  115.  
  116. 	cout<<dp[n][m];
  117.  
  118.  
  119.  
  120. 	return 0; 
  121. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
awbc
u
stdout
copy 
3
https://ideone.com/ePE8EY
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!