problem link:
https://www.codechef.com/CLAG2020/problems/DYNMCPRG
Author:dhussa_09 | CodeChef User Profile for Tejas Dhussa | CodeChef
Tester:dhussa_09 | CodeChef User Profile for Tejas Dhussa | CodeChef
Translator:dhussa_09 | CodeChef User Profile for Tejas Dhussa | CodeChef
Editorialist:dhussa_09 | CodeChef User Profile for Tejas Dhussa | CodeChef
DIFFICULTY:
EASY-MEDIUM
** PREREQUISITES:**
DYNAMIC PROGRAMMING
PROBLEM:
The chef has n arrays each array has an m number of elements. For each array given, You have to find the maximum sum of a subsequence with the constraint that no two numbers in the sequence should be adjacent to each other in the array and store it in the new array which will be of the size n. Now, you have a single new array of size n. From that find the minimum sum of a subsequence by using the maximum number of elements in an array with the constraint that no two numbers in the sequence should be adjacent to each other in the array and print it.
EXPLANATION:
Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.
Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).
At the end of the loop return max of incl and excl.
Example:
arr[] = {5, 5, 10, 40, 50, 35}
incl = 5
excl = 0
For i = 1 (current element is 5)
incl = (excl + arr[i]) = 5
excl = max(5, 0) = 5
For i = 2 (current element is 10)
incl = (excl + arr[i]) = 15
excl = max(5, 5) = 5
For i = 3 (current element is 40)
incl = (excl + arr[i]) = 45
excl = max(5, 15) = 15
For i = 4 (current element is 50)
incl = (excl + arr[i]) = 65
excl = max(45, 15) = 45
For i = 5 (current element is 35)
incl = (excl + arr[i]) = 80
excl = max(65, 45) = 65
And 35 is the last element. So, answer is max(incl, excl) = 80
DO IT FOR ALL n ARRAYS WITH ELEMENTS m.
finally, you will get an array of size n.
after this, you have to find the minimum sum of a subsequence by using the maximum number of elements in an array with the constraint that no two numbers in the sequence should be adjacent to each other in the array and print it.
Its very simple use of basic maths for this condition.
As, 1<=n<=4.we have 3 condtiions.
As we have print minimum sum by taking maximum elements which eliminate adjacent element.
1]if(x == 4)
{
//eg- if new array created of size n has elements [1,8,9,2],result=3.
//print minimum sum by taking maximum elements which eliminate adjacent element.
//here they will eliminate 8 and 9.AS 8 is adjacent to 1 and 9 is adjacent to 2.
result = min(ans[1] + ans[4], result);
result = min(ans[1] + ans[3], result);
result = min(ans[2] + ans[4], result);
}
2] else if(x == 3)
{
//eg- if new array created of size n has elements [5,4,8],result=4.
// print minimum sum by taking maximum elements which eliminate adjacent element.
result = min(result, ans[1] + ans[3]);
result = min(result, ans[2]);
}
3] else if(x == 2)
{
//eg- if new array created of size n has elements [55,109],result=55.
result = min(ans[1], ans[2]);
}
4] else
{
//eg- if new array created of size n has elements [8],result=8.
result = ans[1];
}
The solution in c++14 language:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll cal(vector &a)
{
int n = a.size();
vector dp(n, 0);
dp[1] = a[1];
dp[2] = max(a[1], a[2]);
for(int i = 3; i<n; ++i)
{
dp[i] = max(dp[i-1], dp[i-2] + a[i]);
}
return dp[n - 1];
}
int main()
{
int t;cin>>t;
while(t–){
int n, m; cin>>n>>m;
vector ans; ans.push_back(0);
int x = n;
while(n–){
vector a(m + 1, 0);
for(int i=1; i<=m;++i) cin>>a[i];
if(m == 1)
{
ans.push_back(a[1]);
continue;
}
else ans.push_back(cal(a));
}
ll result = INT_MAX;
if(x == 4)
{
// 1,4 1,3 2,4
result = min(ans[1] + ans[4], result);
result = min(ans[1] + ans[3], result);
result = min(ans[2] + ans[4], result);
}
else if(x == 3)
{
//1,3 2
result = min(result, ans[1] + ans[3]);
result = min(result, ans[2]);
}
else if(x == 2)
{
result = min(ans[1], ans[2]);
}
else
{
result = ans[1];
}
cout<<result<<endl;
}
// cerr << "\nTime elapsed: "<< 1000 * clock() / CLOCKS_PER_SEC << “ms\n”;
return 0;
}