POJ1390--blocks.rar

/******************************************************************************* Source Code Problem: 1390 User: new_star Memory: 32040K Time: 1578MS Language: C++ Result: Accepted *******************************************************************************/ //Source Code #include<iostream> using namespace std; int color[201] , len[201], score[201][201][201], boxesNum, colorsNum; int main( void ) { int dp( int, int, int ); int casesNum; cin >> casesNum; for ( int cn = 1; cn <= casesNum; cn++ ){ int tmp; len[1] = 1; colorsNum = 1; cin >> boxesNum; cin >> color[colorsNum]; for ( int bn = 2; bn <= boxesNum; bn++ ){ cin >> tmp; if ( tmp == color[colorsNum] ) len[colorsNum]++; else{ colorsNum++; color[colorsNum] = tmp; len[colorsNum] = 1; } } for ( int i = 0; i <= colorsNum; i++ ) for ( int j = 0; j <= colorsNum; j++ ) for ( int k = 0; k <= boxesNum; k++ ) score[i][j][k] = -1; cout << "Case " << cn << ": " << dp( 1, colorsNum, 0 ) << endl; } return 0; } int dp( int i, int j, int k ) { int sum; if ( score[i][j][k] >= 0 ) return score[i][j][k]; if ( j+1 == i && k == 0 ) return 0; sum = dp( i, j-1, 0 )+(len[j]+k)*(len[j]+k ); for ( int jj = j-1; jj >= i; jj-- ) if ( color[jj] == color[j] ){ int tmp = dp( i, jj, k+len[j] )+dp( jj+1, j-1, 0 ); if ( sum < tmp ) sum = tmp; } score[i][j][k] = sum; return score[i][j][k]; }