➤ Problem Link : MAIN112
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n],c[n];
for(int i=0;i<n;i++)
cin>>arr[i];
for(int i=0;i<n;i++)
cin>>c[i];
if(n==1)
{
cout<<"0\n";
continue;
}
ll val=pow(2,n)-1;
ll dp[val+1][n];
for(ll i=0;i<=val;i++)
for(ll j=0;j<n;j++)
dp[i][j]=INT_MAX;
for(int i=0;i<n;i++)
dp[1<<i][i]=0;
ll ans=INT_MAX;
for(ll i=1;i<=val;i++)
{
int cnt=__builtin_popcount(i);
for(ll j=0;j<n;j++)
{
if(!(i & (1<<j)))
continue;
for(ll k=0;k<n;k++)
{
if(i & (1<<k))
continue;
dp[i | (1<<k) ][k]=min(dp[i | (1<<k) ][k],dp[i][j]+abs(arr[k]-arr[j])*c[cnt]);
if(cnt==n-1)
{
ans=min(ans,dp[i | (1<<k) ][k]);
}
}
}
}
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.