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