PROBLEM LINK:
Author: Aniswar Srivatsa Krishnan
Editorialist: Shriram Chandran
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, basic BFS/path traversal.
PROBLEM:
Given an array, find the maximum sum possible by optimally clubbing few adjacent elements and replacing them by their product.
EXPLANATION:
Let us do a simple dp and also keep a separate parent array p.
Initially, dp_1=a_1 and p_1=0.
dp_2=max(a_1+a_2,a_1*a_2). if(dp_2=a_1*a_2), p_2=0, otherwise p_2=1.
Now for the general case, the transitions are clear: if dp_{i-1}+a_i > dp_{i-2} + a_{i-1}*a_i, then dp_i = dp_{i-1}+a_i and p_i = i-1. Otherwise, dp_i = dp_{i-2} + a_{i-1}*a_i and p_i = i-2.
Now, the optimal value is obtained in dp_n.
How do we obtain the set of pairs of missiles to be fused?
This is where the p array becomes useful. Start from n, and keep traversing the p array using i=p_i. Whenever p_i = i-2, the elements a_i and a_{i-1} were fused in the optimal answer. Store all such i and output the pairs correspondingly.
Note that multiple answers are possible due to equality conditions. All the optimal correct answers are awarded AC verdict.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a>b)?a:b)
using namespace std;
void solve()
{
ll n;
cin>>n;
ll a[n];
for(ll i=0;i<n;i++)
cin>>a[i];
ll dp[n][2];
for(ll i=0;i<n;i++)
dp[i][0]=dp[i][1]=-1e18;
dp[0][0]=a[0];
dp[0][1]=-1;
dp[1][0]=a[0]+a[1];
if(a[1]*a[0]>dp[1][0])
{
dp[1][0]=a[1]*a[0];
dp[1][1]=-1;
}
else dp[1][1]=0;
for(ll i=2;i<n;i++)
{
dp[i][0]=dp[i-1][0]+a[i];
if(dp[i-2][0]+a[i]*a[i-1]>=dp[i][0])
{
dp[i][0]=dp[i-2][0]+a[i]*a[i-1];
dp[i][1]=i-2;
}
else dp[i][1]=i-1;
}
vector<pair<ll,ll>> ans;
ll i=n-1;
while(i!=-1)
{
if(dp[i][1]==i-2)
ans.push_back(make_pair(i,i+1));
i=dp[i][1];
}
cout<<dp[n-1][0]<<" "<<n-ans.size()<<endl;
cout<<ans.size()<<endl;
for(auto i:ans)
cout<<i.first<<" "<<i.second<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}