PROBLEM LINK:
Author: Abhijeet Trigunait
Tester: Abhijeet Trigunait
DIFFICULTY:
MEDIUM .
PREREQUISITES:
DP,Binary Search.
PROBLEM:
Chef has very beautiful garden.There are N flower plants arranged in row.The height and beauty of ith flower from left is hi and bi.In order to make garden less crowdy chef decided to pull out some flower plants.
But chef has one condition in mind that needs to be met while pulling flower plants.
- The heights of the remaining flower plants must be monotonically increasing from left to right.
Your task is to help Chef to find the maximum possible sum of the beauties of the remaining flower plants.
EXPLANATION:
We can rephrase the above question as to find the increasing subsequence whose sum of beauty is maximum.We can solve this problem using 1d dp ,with each index representing the subsequence ending at ith element which is monotonically increasing and has maximum sum.
so dp[i] =the sum of the increasing subsequence ending at ith index and has maximum sum, where 1<=i<=n.
and the maximum of the dp array would be answer.
for i=1 ,maximum possible sum would simply be beauty of first flower plant.
so,
dp[1]=bty[1].
and for all i dp[i] is given by:
dp[i]=max( bty[i] , bty[i] + max(dp[j] ,where 1<=j<i and hj<hi)
here dp[j] corresponds to the subsequence which we are extending with ith index.
Time complexity for the above approach would be O(N^2),so its not the efficient one.
We can reduce the complexity by using better approach to find dp[j] so as to calculate dp[i].
To get the best previous index which can be extended ,we can maintain a data structure (map) instead of iterating j from 1 to i ,that would only contain the meaningful indices that can be extended and can contribute for maximum sum ,and in process we would also delete unnecessary indices.
For ex:
if j<i
dp[j]<dp[i]
hj>hi
hi: 1 2 3
bi 2 1 1
dp[i]: 2 3 4
so here we can see that ,removing the jth index won’t affect our answer ,in above example we can remove the index with height 1 .
For searching the heights that is just less than the current index height and sum is maximum ,we can simply use lower bound function and will update dp[i] .Also if it result in meaningful indices we would push it on the map, and will also remove unnecessary indices at each step.
Following above approach we can solve the problem inO(N logN).
SOLUTIONS:
Setter's Solution
/* Author- Abhijeet Trigunait */
#include<bits/stdc++.h>
#define lld long long int
#define F first
#define S second
#define P pair<int,int>
#define pb push_back
#define mod 1e9+7
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define gcd(x,y) __gcd(x,y)
#define endl '\n'
using namespace std;
struct flower {
lld hi;
lld byt;
};
lld solve(vector<flower>& vec, lld n) {
vector<lld> dp(n + 1);
map<lld, lld> mp;
dp[1] = vec[1].byt;
mp[vec[1].hi] = dp[1];
lld ans = dp[1];
for (lld i = 2; i <= n; ++i) {
dp[i] = vec[i].byt;
auto it = mp.lower_bound(vec[i].hi +1);
if(it !=mp.begin()){
--it;
dp[i] += it->second;
}
mp[vec[i].hi] = dp[i];
it = mp.upper_bound(vec[i].hi);
while (it != mp.end() and it->second <= dp[i]) {
auto temp = it;
temp++;
mp.erase(it);
it = temp;
}
ans = max(ans, dp[i]);
} return ans;
}
int main() {
int t;
cin>>t;
while(t--){
lld n;
cin >> n;
vector<flower> vec(n + 1);
for (lld i = 1; i <= n; ++i)cin >> vec[i].hi;
for (lld i = 1; i <= n; ++i)cin >> vec[i].byt;
cout << solve(vec, n) << endl;}
}