I have written the recursive solution for the problem: CodeChef: Practical coding for everyone
I need help as I am not aware of how to apply dp to my solution. Thank you in advance!
My sol:
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define er erase
#define MP make_pair
#define fastio \
ios_base::sync_with_stdio(0); \
cin.tie(NULL); \
cout.tie(NULL)
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;
typedef long long int ll;
using namespace std;
ll lcm(ll a, ll b)
{
return (a * b) / __gcd(a, b);
}
ll power(ll a, ll b)
{
if (b == 0)
{
return 1;
}
ll curr = 1;
while (b != 1)
{
if (b % 2 != 0)
{
curr = curr * a;
a = a * a;
b = b - 1;
b = b / 2;
}
else
{
a = a * a;
b = b / 2;
}
}
return curr * a;
}
bool isprime(ll n)
{
bool flag = true;
if (n == 2 or n == 3 or n == 5 or n == 7 or n == 11)
{
flag = true;
}
else
{
for (ll i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
flag = false;
break;
}
}
}
return flag;
}
// ------------------------------------------------------------------// THE SOLUTION STARTS FROM HERE -------------------------------------
vector<ll> h, q;
ll arr[1001][1001];
ll solve(ll i,ll n,ll pre)
{
if(i==n)
{
return 0;
}
else
{
if(pre==-1)
{
return arr[i][pre]=max(solve(i+1,n,pre),solve(i+1,n,i)+1);
}
else
{
if(h[i]>h[pre] and q[i]<q[pre])
{
return arr[i][pre]=max(solve(i + 1, n, pre), solve(i + 1, n, i) + 1);
}
else
{
return arr[i][pre]=solve(i+1,n,pre);
}
}
}
}
int main()
{
fastio;
ll t;
cin >> t;
while (t--)
{
memset(arr,-1,sizeof(arr));
q.clear();
h.clear();
ll n;
cin >> n;
for (ll i = 0; i < n; i++)
{
ll temp;
cin >> temp;
h.PB(temp);
}
for (ll i = 0; i < n; i++)
{
ll temp;
cin >> temp;
q.PB(temp);
}
cout<<solve(0,n,-1)<<endl;
}
return 0;
}