you are given an array of stones with size n+1 where the initial weight of each stone is 1.
We are playing a game with the stones. At round j starting from 0, we choose any two adjacent stones and combine them together.
Suppose the stones have weight x and y, then the combined stone has weight x+y. This combination requires a cost x*y*v[j].
The quantity v[] is a nonincreasing sequence given to you prior to the game, and changes over rounds.
The game continues with n rounds, and after round nth there is precisely one stone left with weight n+1.
Return the lowest cost you need to pay in total of n rounds.
Input: n=5, v=[4,3,2,0,0] Output: 9
Explanation: [1 1 1 1 1 1]->[2 1 1 1 1]->[2 2 1 1]->[2 2 2]->[4 2]->[6] The output is 1*1*4+1*1*3+1*1*2=9
Input: n=5, v=[4,3,1,1,0] Output: 11
Explanation: [1 1 1 1 1 1]->[2 1 1 1 1]->[2 1 2 1]->[3 2 1]->[3 3]->[6] The output is 1*1*4+1*1*3+2*1*1+2*1*1=11
Input: n=5, v=[4,2,2,1,0] Output: 12
here is what i came up with, it works but it's damn slow time complexity is exponential here. please help if fast solution's are possible
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef array< int , 2 > ar;
typedef set< ar > node ;
node t[50][50];
int solve( vector<int>A , vector<int>B )
{
const int N = A.size();
for( int i = 0 ; i < N ; i++ )
t[i][i] = { { 0 , 0 } };
// t[i][j] -> range -> vector[ bitmask , value ]
// bitmask -> to maintain which rounds have been utilized
int P[A.size()+1];
P[0] = 0 ;
for( int i = 0 ; i < (int)A.size() ; i++ )
P[i+1] = P[i] + A[i] ;
auto get = [&]( int a , int b )
{
return P[b+1] - P[a] ;
};
auto work = [&]( int i , int j , int k , node &left , node &right ) -> void
{
for( auto x : left )
for( auto y : right)
{
int b1 = x[0] ;
int b2 = y[0] ;
int v1 = x[1] ;
int v2 = y[1] ;
if( (b1|b2) == (b1^b2) )
{
int used = b1|b2 ;
for( int round = 0 ; round < (int)B.size() ; round++ )
{
int p = 1<<round ;
if( (p^used) == (p|used))
{
int myBitMask = used|(1<<round) ;
t[i][j].insert({ myBitMask , v1 + v2 + (get( i , k) * get( k+1 , j) * B[round]) });
}
}
}
}
};
for( int L = 2 ; L <= N ; L++ )
for( int i = 0 ; i+L-1<N; i++ )
{
int j = i+L-1;
for( int k = i ; k < j ; k++ )
work( i , j , k , t[i][k] , t[k+1][j] );
}
int mn = INT_MAX ;
for( auto x : t[0][N-1] )
mn = min( mn , x[1] );
return mn ;
}
int main() {
// your code goes here
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N;
cin>>N ;
vector<int>A(N+1,0);
vector<int>B(N);
for( auto &x : A )
cin>>x ;
for( auto &x : B )
cin>>x ;
cout<<solve( A , B )<<endl;
return 0;
}
/*
5
1 1 1 1 1 1
4 3 1 1 0
-> 11
5
1 1 1 1 1 1
4 3 2 0 0
-> 9
*/