### second_saturday's blog

By second_saturday, history, 9 months ago,

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))
{
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() {

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
*/

• 0