/* * Solution to problem: http://community.topcoder.com/stat?c=problem_statement&pm=1996&rd=4710 (SRM-178, DIV-1, hard) * * Vamsi K. Kundeti 10/05/2012 * **/ #include#include #include #include #include using namespace std; #define MAX_ROWS 50 #define MAX_STROKES 3000 class MinPaint { private: /*Optimal number of mismatches to color a row 'i' till 'j' with a *stoke ending black using 'k' strokes : 'm_aB[j%2][i][k]' */ size_t m_aB[2][MAX_ROWS][MAX_STROKES]; size_t m_aW[2][MAX_ROWS][MAX_STROKES]; /*Optimal number of mismatches in the image upto row 'i' using 'k' *strokes*/ int m_aOPT[2][3001]; //optimal value is stored in m_aB[0][i][j] vector m_aImg; public: MinPaint(): m_aB(), m_aW(), m_aImg() {} void initRow(size_t idx, size_t maxStrokes){ for(size_t j=0; j<=maxStrokes; j++){ m_aB[0][idx][j] = !j ? 1 : m_aImg[idx][0] == 'W'; m_aW[0][idx][j] = !j ? 1 : m_aImg[idx][0] == 'B'; } } size_t findMin(size_t a, size_t b){ return a < b ? a : b; } void dynamicProgramPerRow(size_t idx, size_t maxStrokes){ initRow(idx, maxStrokes); for(size_t i=1; i < m_aImg[idx].size(); i++){ for(size_t j=0; j <= maxStrokes; j++){ if(m_aImg[idx][i] == 'W'){ m_aW[i%2][idx][j] = !j ? i+1 : findMin(m_aW[(i-1)%2][idx][j], m_aB[(i-1)%2][idx][j-1]); m_aB[i%2][idx][j] = !j ? i+1 : findMin(m_aB[(i-1)%2][idx][j]+1, m_aW[(i-1)%2][idx][j-1]+1); }else{ m_aB[i%2][idx][j] = !j ? i+1 : findMin(m_aB[(i-1)%2][idx][j], m_aW[(i-1)%2][idx][j-1]); m_aW[i%2][idx][j] = !j ? i+1 : findMin(m_aW[(i-1)%2][idx][j]+1, m_aB[(i-1)%2][idx][j-1]+1); } } } //choose the min between m_aB and m_aW size_t nidx = m_aImg[idx].size()-1; for(size_t i=0; i<=maxStrokes; i++){ m_aB[nidx%2][idx][i] = findMin(m_aB[nidx%2][idx][i], m_aW[nidx%2][idx][i]); } } int leastBad(const vector &Img, const int &maxStrokes){ m_aImg = Img; for(size_t i=0; i< Img.size(); i++){ dynamicProgramPerRow(i, (size_t)maxStrokes); } //now find the optimal across rows// for(int i=0; i<=maxStrokes; i++){ m_aOPT[0][i] = m_aB[(Img[0].size()-1)%2][0][i]; } for(size_t j=1; j<Img.size(); j++){ /*choose number of strokes from [1, maxStrokes-j] to paint row 'j'*/ size_t rsize_idx = m_aImg[j].size()-1; for(int usedStrokes=0; usedStrokes<=maxStrokes; usedStrokes++){ int min = numeric_limits ::max(); int current_min; int min_k=0; for(int k=0; k<=usedStrokes; k++){ //use 'k' strokes to color current row 'j' and 'usedStrokes-j' for the //array below 'j'. current_min = m_aOPT[(j-1)%2][usedStrokes-k] + (m_aB[(rsize_idx)%2][j][k]); if(current_min < min){ min = current_min; min_k = k; } } m_aOPT[j%2][usedStrokes] = min; } } return m_aOPT[(Img.size()-1)%2][maxStrokes]; } size_t OptPerRow(size_t idx, size_t maxStrokes){ return m_aB[(m_aImg[idx].size()-1)%2][idx][maxStrokes-1]; } }; /*INPUT FILE FORMAT: * * * X Y * string1 * string2 * ... * ... * ... * stringX * *X is the number of rows *Y is the maximum number of strokes **/ int main(int argc, char **argv){ char buf[4096]; vector input; size_t imgSize, maxStrokes; MinPaint X; while(scanf("%lu%lu", &imgSize, &maxStrokes)==2){ input.clear(); while(imgSize-- && scanf("%s", &buf) == 1){ input.push_back(string(buf)); } int opt = X.leastBad(input, maxStrokes); printf("%d\n", opt); } }
Have fun -- because you can afford it only on a Friday.
Vamsi.
