/* FILE: stomp2x3over2xn.cpp last change: 30-Sep-2013 author: Romeo Rizzi * an O(n) time and memory DP solver for problem stomp2x3over2xn. */ //#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 INFTY = INT_MAX; const int MAX_N = 1000000; int n; int p[2][3]; // p[0][0] p[0][1] p[0][2] // p[1][0] p[1][1] p[1][2] this is the footprint of the STOMP ! int s[2][MAX_N]; // s[0][0] s[0][1] ... s[0][n-1] // s[1][0] s[1][1] ... s[1][n-1] this is the input strip ! int minOnes[MAX_N -1][ 2][ 2][ 2][ 2]; /* D00 | D01 * D00 D10 D01 D11 are the 4 binary entries of matrix D = ----+---- * D10 | D11 * for i = n-2 downto 0 * minOnes[i][D00, D10, D01, D11] is the minimum number of 1's which will remain in the suffix substrip s[i+2 ... n-1] after applying a set of stomps * fully contained within the suffix substrip s[i ... n-1] and with the constraint that s[i, i+1] becomes equal to D with the application of these stomp. * The optimal solution value for the original problem is min_D minOnes[0][D]. * / 0 if D = s[n-2,n-1] * BASE: minOnes[n-2][ D ] = < * \ INFTY otherwise * * STEP: for i < n-2, in order to compute minOnes[i][D], guess the content of s[i+2] after the application of a set of stomps realizing minOnes[i][D]. * X0 * Let X = -- denote this guess, and also guess whether you will fit a stomp into s[i ... i+2]. * X1 * Now all the guessing is complete and will univocally trigger a recurrence. Clearly, you will opt for the best (min) guess. */ int main() { ifstream fin("input.txt"); assert( fin ); fin >> n; for(int i = 0; i < 2; i++) for(int j = 0; j < 3; j++) fin >> p[i][j]; for(int i = 0; i < 2; i++) for(int j = 0; j < n; j++) fin >> s[i][j]; // BASE: for(int D00 = 0; D00 < 2; D00++) for(int D10 = 0; D10 < 2; D10++) for(int D01 = 0; D01 < 2; D01++) for(int D11 = 0; D11 < 2; D11++) minOnes[n-2][D00][D10][D01][D11] = INFTY; minOnes[n-2] [ s[0][n-2] ][ s[1][n-2] ][ s[0][n-1] ][ s[1][n-1] ] = 0; // STEP: for(int i = n-3; i >= 0; i--) for(int D00 = 0; D00 < 2; D00++) for(int D10 = 0; D10 < 2; D10++) for(int D01 = 0; D01 < 2; D01++) for(int D11 = 0; D11 < 2; D11++) { minOnes[i][D00][D10][D01][D11] = INFTY; // we are gonna to take the best over all admissible guessings for(int X0 = 0; X0 < 2; X0++) for(int X1 = 0; X1 < 2; X1++) { // the guess over X: if( (s[0][i] == D00) && (s[1][i] == D10) ) // if s[i] = D[0] then not to fit a stomp into s[i ... i+2] is an admissible guessing if( minOnes[i+1][D01][D11][X0][X1] < INFTY ) minOnes[i][D00][D10][D01][D11] = min( minOnes[i][D00][D10][D01][D11], X0+X1 + minOnes[i+1][D01][D11][X0][X1] ); if( ( (s[0][i]+p[0][0])%2 == D00) && ( (s[1][i]+p[1][0])%2 == D10) ) // if fitting a stomp into s[i ... i+2] is an admissible guessing ... if( minOnes[i+1][(D01+p[0][1])%2][(D11+p[1][1])%2][(X0+p[0][2])%2][(X1+p[1][2])%2] < INFTY ) minOnes[i][D00][D10][D01][D11] = min( minOnes[i][D00][D10][D01][D11], X0+X1 + minOnes[i+1][(D01+p[0][1])%2][(D11+p[1][1])%2][(X0+p[0][2])%2][(X1+p[1][2])%2] ); } } int opt = INFTY; // lets compute opt = min_D minOnes[0][D] for(int D00 = 0; D00 < 2; D00++) for(int D10 = 0; D10 < 2; D10++) for(int D01 = 0; D01 < 2; D01++) for(int D11 = 0; D11 < 2; D11++) if( minOnes[0][D00][D10][D01][D11] < INFTY ) opt = min( opt, minOnes[0][D00][D10][D01][D11] +D00 +D10 +D01 +D11 ); ofstream fout("output.txt"); assert( fout ); fout << opt << endl; fout.close(); return 0; }