How to apply convex hull optimization in dynamic programming?

695 views Asked by At

I am trying to solve this problem on codeforces using dynamic programming. I have made the recurrence which is of O(N^2) complexity but it is timing out. I know that the complexity of this solution can be reduced to O(N) via Convex hull optimization which is explained here. But I am not able to reduce the complexity. Please help.

This is my code.

#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
typedef long long ll;
ll a[MAX],b[MAX],dp[MAX];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    dp[0] = 0;

    for(int i = 1; i < n; i++)
    {
        dp[i] = 1e18;
        for(int j = 0; j < i; j++)
        {

            dp[i] = min(dp[i],dp[j] + a[i] * b[j]);
        }
    }

    cout << dp[n-1];
}
0

There are 0 answers