/* FILE: triplette2.cpp last change: 12-Sept-2012 author: Romeo Rizzi * an optimal (quadratic) solver for problem "triplette" */ #define NDEBUG // NDEBUG definita nella versione che consegno #include #ifndef NDEBUG # include // uso di cin e cout non consentito in versione finale #endif #include #include using namespace std; const int UNFEASIBLE = INT_MAX; const int MAX_N = 10000; // massima cardinalita' dell'insieme di numeri fornito in input int n, vect[MAX_N]; /* assumes the input integers have been sorted so that vect[0], ..., vect[n-1] is non-decreasing. Once this is done, it can be proven that there always exists an optimal solution where the two rightmost elements of each triplet are consecutive. We call these two elements the "head" of the triplet, and search for an optimum solution among those which have this structure (no head is split). minCost[i][numHeads] will store the minimum cost of a partial solution which has placed numHeads full heads within vect[i], ..., vect[n-1]. Furthermore, vect[i] is bound to be either a tail or the first of the two elements of an head. In conclusion, no triplet has precisely one element within vect[i], ..., vect[n-1] and precisely numHeads triplets have at least 2 elements within vect[i], ..., vect[n-1] and we consider only the weight of these triplets. */ int minCostWithout[MAX_N +1][MAX_N/3 +1]; void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; } void sort(int vect[], int n) { if( n > 1 ) { for(int i = 0; i < n-1; i++) if( vect[n-1] < vect[i] ) swap(vect[n-1], vect[i]); sort(vect, n-1); } } #ifndef NDEBUG void displayVect(int vect[], int n) { for(int i = 0; i < n; i++) cout << vect[i] << " "; cout << endl; } #endif int main() { ifstream fin("input.txt"); assert(fin); fin >> n; for(int i = 0; i < n; i++) fin >> vect[i]; fin.close(); //displayVect(vect, n); sort(vect, n); //displayVect(vect, n); minCostWithout[n][0] = 0; minCostWithout[n-1][1] = minCostWithout[n-1][0] = UNFEASIBLE; for(int i = n-2; i >= 0; i--) for(int j = n/3 +1; j >= 0; j--) { if( 2*j > n-i) minCostWithout[i][j] = UNFEASIBLE; //troppe teste in suffisso di soli n-i elementi else if( j < (n-i +2)/3 ) minCostWithout[i][j] = UNFEASIBLE; else { minCostWithout[i][j] = minCostWithout[i+1][j]; if( minCostWithout[i+2][j-1] != UNFEASIBLE ) minCostWithout[i][j] = min( minCostWithout[i][j], minCostWithout[i+2][j-1] + (vect[i]-vect[i+1])*(vect[i]-vect[i+1]) ); #ifndef NDEBUG cout << "minCostWithout[" << i << "][" << j << "] = " << minCostWithout[i][j] << endl; #endif } //cout << "WIDER minCost[" << i << "][" << j << "] = " << minCost[i][j] << endl; } ofstream fout("output.txt"); assert(fout); fout << minCostWithout[0][n/3] << endl; fout.close(); return 0; }