ABC #162 F - Select Half
Problem Statement - here
Solution -> We will be using 1d DP to solve the problem. We will make the prefix sum array for odd positions beforehand. Let's denote it as ps[ ]. (eg -> ps[5] = ps[3] + a[5])
So, let's break the problem into 2 halves ->
- When the current index in consideration (i) is odd
- When i is even.
Case 01 - When i is even:
We need to choose exactly i/2 elements.
SO, dp[i] = max(dp[i-2]+a[i],ps[i-1]).
Let's understand the above line -
I have 2 choices for the current index:
- If i include current index in my answer, then the problem reduces to exactly i/2 - 1elements. This is nothing but (i-2)/2. So dp[i-2] comes into play.
- If I decide to leave my current index. Problem reduces to finding max of exactly i/2 elements in the range of [0,i-1] where (i-1)/2 < i/2. And also, there is exactly one sequence, that can give i/2 elements. This is 1,3,5,7,....i-1. So it is nothing but prefix sum of all odd positions up to i-1.
Case 02 - When i is odd:
This case is simple. Since i/2 is same as (i-1)/2, we can transform this as
dp[i] = max(dp[i-1],a[i]+dp[i-2])
Let's understand this line.
dp[i-1] is fairly clear. It comes if I decide not to pick my current element. Then it is the same as a subproblem of size i-1. Because even in the subproblem of size i-1. I need to pick exactly i/2 elements.
But, If I want to pick up my current element, the subproblem reduces to i-2. So a[i] + dp[i-2] comes into picture. This happens because, If i pick up an element, the problem reduces to exactly picking up i/2 - 1 more elements. This is nothing but (i-2)/2. So the problem reduces to dp[i-2].
Code -
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl '\n'
#define rep(i,a,b) for(ll i=a;i<b;i++)
void solve()
{
ll n;
cin>>n;
ll a[n+1];
rep(i,1,n+1) cin >> a[i];
ll ps[n+1],dp[n+1];
dp[0] = 0;dp[1] = 0;
ps[1] = a[1];
for(ll i=3;i<=n;i+=2) ps[i] = ps[i-2] + a[i];
rep(i,2,n+1){
if (i&1){
dp[i] = max(dp[i-1],a[i]+dp[i-2]);
}
else{
dp[i] = max(dp[i-2] + a[i],ps[i-1]);
}
}
cout << dp[n] << endl;
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
return 0;
}
