fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. vector< vector<int> > mat;
  5. const int INF = 1e6;
  6. int nwa(string a, string b , int i , int j){
  7. 	if(mat[i][j] != -INF) 
  8. 		return mat[i][j];
  9. 	else{
  10. 		int val1;
  11. 		if(i > 0 && j > 0 && a[i - 1] == b[j - 1])
  12. 			val1 = nwa(a , b, i - 1, j - 1) + 1; 
  13. 		else
  14. 			val1 = nwa(a , b, i - 1, j - 1) - 1;
  15. 		int val2 = nwa(a , b, i - 1, j) - 2;
  16. 		int val3 = nwa(a , b, i, j - 1) - 2;
  17. 		return mat[i][j] = max({val1 , val2 , val3});
  18. 	}
  19. }
  20.  
  21.  
  22. signed main() {
  23. 	cin.tie(NULL);
  24. 	ios_base::sync_with_stdio(NULL);
  25. 	string a = "AAAC";
  26. 	string b = "AGC";
  27. 	int m = a.size();
  28. 	int n = b.size();
  29. 	mat.assign(m + 1, vector<int>(n + 1, -INF));
  30. 	int cnt = 0;
  31. 	for(int i = 0 ; i <= n; i++) mat[0][i] = cnt, cnt -= 2; 
  32. 	cnt = 0;
  33. 	for(int i = 0 ; i <= m; i++) mat[i][0] = cnt, cnt -= 2;
  34. 	int ans = nwa(a , b,  m , n);
  35. 	for(auto v : mat){
  36. 		for(int i : v)
  37. 			cout << i << "\t\t";
  38. 		cout << endl;
  39. 	}
  40. 	cout << "RES:\n";
  41. 	cout << ans << endl;
  42. 	return 0;
  43. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0		-2		-4		-6		
-2		1		-1		-3		
-4		-1		0		-2		
-6		-3		-2		-1		
-8		-5		-4		-1		
RES:
-1
https://ideone.com/RZ6b4l
language:
C++14 (gcc 8.3)
created:
1 year 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!