second_saturday's blog

By second_saturday, history, 6 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it