Balikavadhu.cpp

/*

				Name: Gourav Singh
				https://www.linkedin.com/in/gouravsingh2580/

*/

/*
Anandi and Jagya were getting married again when they have achieved proper age. Dadi Sa invited 
Alok Nath to do the kanyadaan and give blessings. Alok Nath has 2 blessings. Each bessing is in 
the form of a string consisting of lowercase charaters(a-z) only. But he can give only one
blessing of K length because some priest told him to do so. Thus he decides to generate a
blessing using the other two blessings. While doing this he wants to ensure that happiness 
brought into their life by his blessing is maximum.
The generated blessing is a common subsequence of length K of the two blessings he has. Happiness
of the blessing he generates is calculated by the sum of ASCII values of characters in the blessing
and he wants the happiness to be maximum. If he is not able to generate a common subsequence
of length K then the happiness is 0 (zero). Alok Nath comes to you and asks you to find the maximum 
happiness that can be generated by the two blessings he has.
Input Specification
First line consists of number of test cases t. Each test case consists of two strings b1 (blessing 1),
b2 (blessing 2) and an integer K, each of them in separate lines.
Output Specification
Output consists of t lines each containing an integer denoting the maximum happiness value 
that can be generated by the two blessings.
Constraint
1 <= t <= 50

1 <= length(b1) , length(b2) <= 100 

1 <= K <= 100
Sample Input
2
asdf
asdf
3
anandi
jagya
3
Sample Output
317
0
*/


/*
RECURSIVE SOLUTION WITHOUT DP
int go(string s1, string s2, int k, int i, int j){


	int l1 = s1.size()-i;
	int l2 = s2.size()-j;

	//Recursive solution

	if(k>l1 || k>l2){
		return 0;
	}

	if(k<=0){
		return 0;
	}

	

	if (s1[i] == s2[j])
	{
		//I include the eqaul character
		int go1 = s1[i] + go(s1, s2, k-1, i+1, j+1);
		//If function fails to bring enough characters for i+1, j+1
		if (go(s1, s2, k-1, i+1, j+1) == 0 && k>1)
		{
			go1 = 0;
		}
		//I do not include the equal character
		int go2 = go(s1, s2, k, i+1, j+1) ;
		//Alternatively include them
		int go3 = go(s1, s2, k, i+1, j) ;
		int go4 = go(s1, s2, k, i, j+1) ;
		
		
		return max(go1,max(go2,max(go3,go4)));
		

	}else{

		//Alternatively include them
		int go3 = go(s1, s2, k, i+1, j) ;
		int go4 = go(s1, s2, k, i, j+1) ;
		return max(go3,go4);

	}


}*/

/*
			MEMOIZATION SOLUTION
#include <bits/stdc++.h>
using namespace std;
int maxHappiness(string s1,string s2,int k,int output[][101][101]){
    if(k==0){
       return 0;
    }
    if(s1.size()==0 || s2.size()==0)
        return INT_MIN;
    if(output[s1.size()][s2.size()][k]!=-1)
        return output[s1.size()][s2.size()][k];
    if(s1[0]==s2[0]){
       int option1=maxHappiness(s1.substr(1),s2.substr(1),k-1,output)+s1[0];
       int option2=maxHappiness(s1,s2.substr(1),k,output);
       int option3=maxHappiness(s1.substr(1),s2,k,output);
        int ans=max(option1,max(option2,option3));
        output[s1.size()][s2.size()][k]=ans;
        return ans;
    }
    else{
       int option1=maxHappiness(s1.substr(1),s2,k,output);
       int option2=maxHappiness(s1,s2.substr(1),k,output);
        int ans=max(option1,option2);
        output[s1.size()][s2.size()][k]=ans;
        return output[s1.size()][s2.size()][k];
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        string s1,s2;
        cin>>s1>>s2;
        int k;
        cin>>k;
        int output[101][101][101];
        memset(output,-1,101*101*101*sizeof(int));
        int ans=maxHappiness(s1,s2,k,output);
        if(ans<0)
            cout<<"0"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}	
*/



//DP SOULUTION
#include <bits/stdc++.h>

using namespace std;
int go(string s1, string s2, int k){


	int m = s1.size();
	int n = s2.size();

	int dp[m+1][n+1][k+1];
	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < m+1; ++i)
	{
		for (int j = 0; j < n+1; ++j)
		{
			dp[i][j][0] = 0;
		}
	}

	//starting from n(out of string) in second string
	for (int i = 0; i < m+1; ++i)
	{
		for (int p = 0; p < k+1; ++p)
		{
			dp[i][n][p] = 0;
		}
	}

	//starting from m(out of string) in first string
	for (int i = 0; i < n+1; ++i)
	{
		for (int p = 0; p < k+1; ++p)
		{
			dp[m][i][p] = 0;
		}
	}


	for (int i = m-1; i >= 0; --i)
	{
		for (int j = n-1; j >= 0; --j)
		{
			for (int p = 1; p < k+1; ++p)
			{
				if(s1[i] == s2[j]){
					if (p>m-i || p>n-j)
					{
						dp[i][j][p] = 0;
				
						continue;
					}


					int go1 = int(s1[i]) + dp[i+1][j+1][p-1];
					//If function fails to bring enough characters for i+1, j+1
					if (dp[i+1][j+1][p-1] == 0 && p>1)
					{
						go1 = 0;
					}
					//I do not include the equal character
					int go2 = dp[i+1][j+1][p] ;

					//Alternatively include them
					int go3 = dp[i+1][j][p] ;
					int go4 = dp[i][j+1][p] ;
			
					dp[i][j][p] = max(go1,max(go2,max(go3,go4)));
				

				}else{
					if (p>m-i || p>n-j)
					{
						dp[i][j][p] = 0;
						continue;
					}
					int go3 = dp[i+1][j][p] ;
					int go4 = dp[i][j+1][p] ;

					dp[i][j][p] = max(go3,go4);


				}
			}
		}
	}


	return dp[0][0][k];


}	


int main( int argc , char ** argv )
{
	ios_base::sync_with_stdio(false) ; 
	cin.tie(NULL) ; 
	
	int n;
	cin>>n;

	while(n--){
		string s1, s2;
		int k;
		cin>>s1>>s2>>k;

		cout << go(s1, s2, k) << '\n';
	}


	return 0 ; 



}