MiniPaint.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <sstream>
#include <set>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <time.h>
using namespace std;
#define SIZEOFSTRINGARRAY(s) sizeof(s)/sizeof(s[0])
/* https://www.topcoder.com/stat?c=problem_statement&pm=1996&rd=4710 */
/* solution ref topcoder*/

class MiniPaint
{
public:
	int leastBad(vector<string> picture, int maxStrokes);
};
vector<int> dostr(string ss) {
	int n = ss.length() + 1;

	vector< vector<int> > w( n, vector<int> (n) );
	for (int i = 0; i < n; i++) {
		w[i][0] = i;
	}
	for (int at = 1; at <= ss.length(); at++) {
		for (int j = 0; j < n; j++) {
			w[at][j] = w[at - 1][j] + 1;
		}
		int countB = 0;
		int countW = 0;
		for (int bef = at - 1; bef >= 0; bef--) {
			if (ss[bef] == 'B')
				countB++;
			else
				countW++;
			int m = std::min(countB, countW);
			for (int k = 1; k < n; k++) {
				w[at][k] = std::min(w[at][k], w[bef][k - 1] + m);
			}
		}
	}
	return w[ss.length()];
}

int MiniPaint::leastBad(vector<string> picture, int maxStrokes)
{
	int size = picture.size();
	vector<int> dp(maxStrokes + 1);
	
	for (int i = 0; i < size; ++i)
	{
		vector<int> a = dostr(picture[i]);
		int nn = picture[i].length();
		vector<int> newbest(maxStrokes + 1);
		for (int j = 0; j <= maxStrokes; j++) {
			newbest[j] = dp[j] + nn;
		}
		for (int j = 0, size = std::min(maxStrokes, (int)a.size()) ; j < size; ++j)
		{
			for (int k = j; k <= maxStrokes; ++k)
			{
				newbest[k] = std::min(newbest[k], a[j] + dp[k - j]);
			}
		}
		dp.swap(newbest);
	}
	return dp[maxStrokes];
}

void TEST(vector<string> picture, int maxStrokes, int expected)
{
	clock_t start, end;
	double cpu_time_used;

	start = clock();
	MiniPaint miniPaint;

	int result = miniPaint.leastBad(picture, maxStrokes);
	
	assert( result == expected );

	end = clock();
	cpu_time_used = ((double) (end - start));
	cout<<"Time taken : "<<cpu_time_used<<endl;
}

vector< vector<int> > convert(string *list, int n)
{
	vector< vector<int> > ret(n, vector<int> (n));

	for (int i = 0; i< n; ++i)
	{
		string str = list[i];

		for (int j = 0, len = str.length(); j < len; ++j) {
			istringstream iss(str.substr(j,1));

			iss >> ret[i][j];
		}
	}

	return ret;
}

vector<string> convertEx(string *list, int n)
{
	vector<string> ret;

	for (int i = 0; i< n; ++i)
	{
		ret.push_back(list[i]);
	}

	return ret;
}

void Test1()
{
	dostr("BBWWBBBWWW");
	string test[]= {
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"};

TEST(convertEx(test, SIZEOFSTRINGARRAY(test)), 4, 5);
}

void Test2()
{
	string test[]= {
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"};

TEST(convertEx(test, SIZEOFSTRINGARRAY(test)), 6, 0);
}

void Test3()
{
	string test[]= {
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW",
"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW"};

TEST(convertEx(test, SIZEOFSTRINGARRAY(test)), 100, 40);
}

void Test4()
{
	string test[]= {
"BBBBBBBBBBBBBBB",
"WWWWWWWWWWWWWWW",
"WWWWWWWWWWWWWWW",
"WWWWWBBBBBWWWWW"};

TEST(convertEx(test, SIZEOFSTRINGARRAY(test)), 0, 60);
}

void Test5()
{
	string test[]= {"BBBWWWWBWWWWBBWWWBWWWBWBWBBBWWWWBWWBWBWBWWBBBWBBWW", "BWBWBWBWWWBWWBWBWWBWWBBWBBWWWWWBWWBBWBWWBBBWBBBWBB", "BWWBBWBBBBBWWWBWWBWWBWBWBBBBBWWBBBWBWWBWWBBBBBBWWW", "BWWWBWWBBBWBBWWWBWBWBBBWWBBBWBBWBBWBWBBBWBBBWWBBBB", "WWBWBWWBBWWBBBWWWBWWWBWBWBBBBWBBWWBBBWBWWBBWBWBWWB", "BWWWWBWWBWWWWWBBBWWBWWBWWBBWBBWWBWWWWWWBBWWWWWWBWW", "WBWWBWBWWBWBBBWWBWBBWWBWWWWWBBBWWWWWWWWBWWBWBBWBWW", "BWBBWBWWWWWBWBBBBWBBBBBBWBWBBBWBWBWWBBWBBWBBWWBBWB", "BBBBBWWBWWWWWBWWWBBBBWBWWBBWBWBWBBWBBBWBBWWBBWWWWB", "BWBWBBWWBWBBWWBWWWBBBBBBBWBBWWWBWBWWBBBWWBBWWBWBBB", "BBBWWBWBBWWBBWBBBWBBWBBWWBBWWWWWWWWBBBWWWBBBWWBWWW", "WBBBBBWWWBWWWWBWBBWBWBWWWBWWBBWBBWBWWBBBBBWWBWWBBW", "BWWBBWBWBWWWWWBBWBWWBBWWBWWBBBWWBBBWBBWWBWBBBBBWWB", "WWWWBWBWWBBBWWBBWBWBWWBBBBBBWBBBBBBBBBWBWBBBWBWWWB", "WWBBBWBWWBWWBWBBWWWBWWWBWWWBBBBBBBWWBWBBBWWWWBWBWB", "WWWBBBWBBBWBWWWBBWBWBWBWWWBBBBBWBWBWWWWWBBBWWBWBWW", "BWBBBWBWWBWWWBWBWWWBBWWBBWBWWBBWWBWBBBWBWBWWBWWBBB", "WWWBBWBWWBBBBWBBBBWBWBWBBWWWWWBBBWWWBBWWBBBBBBBWWW", "WWBWBWWWBBBBWWBBWBWWWWWBBWBWBBWBWBWBWBBWBWWBWBWBWW", "BBWBWWBBWBBWBWWWWWBBWBWBBWBWWWWWBWBBWBBBBBWWWBBWWW", "BBBWWWBWWBBWBBWBBWWWBWWBBBWWWWWBBBBBWWWBWWBWBBWBBW", "WBWWBBWWBBWBWWBBWBWBWBBBBBBWBWBWWWWWBBWBBBWBBBWWWB", "WBBBWBBWBWWWBBWBBBBWBWWWBWWWWBBWWWBWBWBWBBWWBWBBBB", "BWWWWBWBBBBWBWBBWBBBWBWBWBWBBWWWBWWBWBWBBBBWWBBWBW", "BBWBWBWBBBWBBWWBWWWWBBWWBWBWWWBBWBBBBWBWBWWBWBBWBW", "WWWBWWWWBBBBBBBWBWWBWBWBBWBWWBWBWWWBBBWBBBWWBWWBBB", "WWWWWWBBWWWBWBWWBBBWWWWBWBWBBBWWBWBBBBBBWWWBWBWBWW", "WBBBBBBWWBWBBWWWWWBBWWWWBBBWBWBBBBWBWWBBBWBWBBWWWW", "BBWWBWWBWWBWBBWWBBBWWBWBWBWBBWBWBWBBBWBBBBWWBBBBBB", "BBWBWBBWBBWWBBBWBWBBBBWWBBBWWBBBWWBWBBWBBBWBBBBBBB", "WWWWWBWBBWWWBBWWWWWWBBWBWBBWBBBWWBWBWWWWWBWWWBBWWW", "WWWBBWWBWBBBBWWWBWBWWWBBBBBBBWWBWBWWWBWWWWWWBBWBWB", "BBWBWWWBWWWWWBBBBBBWBWBBWWWWBBWBBWBBBBWBWBBBWWBBWB", "BWBWWWWBBWBBBBWWWBBWWWWBBBWWWBBBBWWWWWWWBBWWWBWWBW", "WWWBWBBBWBWWBWWWWWWBWWWBWBWWBBWBWWBWWWBWBWBWBBBBBW", "WBWWBBWWWBWWWWWWWBBWWBBBBBWWWWWWWBWWWBBWBWWBWBBWBW", "BBWBWWWWBBWWBWWWBBWBWBBWBBBWBWWBWBWBBWWWWWBBWBWWWB", "BBBWBBWWBWWBWWBBWBWBBBWWWWBWBWBBBBBBBWWBBWWBBBWBWB", "WBBWWWBBBWBWWWWWBWWWWWWBBBWWWBBBWBWBWWBBBWWBBBWBWB", "BBBBWBWWWBWBWWWWBWWWBBBWWBWBWWWBBWBBWBWBBWBWWWBWBW", "BBBWWBWWWWBWWWBWBWBBBWWWBWBWBBBBWBBBBBWWBBBBWWBBBW", "BWBWBWBBBBBWBBBWWWWBBWWBWBBBWBBWWBWBWWWBWBBBBWBWWB", "WWBWBWWBBBWWBBWBBBWBBBWBBBBWWBWWWBWWWWWBWWBBWBWWBW", "WWWBBBWWWBBWBWBBWBWWWWBBWBWWWWBWBWBWBWWBBWBBWBWBWW", "WWWBWWWBWWWBBBWWBBBBBBBBWWBBBBBWWBBBWBBBBBBWWBWWWB", "BWBWWBBBWBBWBWWBBWBWWWWBBWBWBBBWWWWBBWBBBWWBBBWBBB", "BBWWWBWBWWBBWWBWBWBWBBWWWWBWBBBBBWBWBBWBWWWBBWBBBW", "BWWWBBWBWBBWBWBWBWWWBWBWBBBBWWBBWBBBBWBBBBWWBBWWBB", "WBBWBWWBBWWBWWBWWWWWWWWBBBBBWWWBBBBWBBWBWWBWBBWWWW", "BBBBBWWBWBBWBWWWWBBWWBBBBWBWWBBBBBBBBBWWWBBWWBBWBW"};

	TEST(convertEx(test, SIZEOFSTRINGARRAY(test)), 139, 825);
}

void Test6()
{
	string test[]= {"BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW", "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBWBW"};
	TEST(convertEx(test, SIZEOFSTRINGARRAY(test)), 3000, 0);
}

void Test7()
{
	string test[]= {"WBBWWBBBWWBWWBWWBWWWBBWBBWWBBWWWBBWWWBWWWBWBBBWBWW", "BWWWWBWBBBWWBBWWWWBBBBWBWBWWBWWBBBBWWBBBBBWBWBBBWW", "BBWWBBBWWWWBBWWWWWBWBBBBBWBWBWWWWBBWWBBBWBWBBBBWWW", "BWWWWWWWBBWWBWWBWWBWBWWBWBWBBWWWBWWBBBBBBBBBWWWBWW", "BWWBWBWWBBWBBBWWBBWWWBWBWBBWWWWWWBWWBWBWWBBBWBWWWB", "WWWWWWBBWBBBBWBBWBBWBWBWBWBBWBWBWWWBWBBBWWBWWBBBBB", "BBWWBBWBWBWWBBWBBBBWBWBWBBWBBWWWWWWWBBBWWWBBBBBWWB", "WWWWBBBBBBWWWWBBBBWBBBWWWBWBWBWWWWBBWWWBBWBBBBBWWB", "WBWWWWWWWBWWBWBWBBBBWBWBBBWBWWBWWWWBWWBWBWWBWBWBBW", "WBWBWWWBWWWBWWBBBWBWWWBBWWWWWBWBWWBBBBBBBBWWBBBWWB", "BBWWBWWWBWBBWWBBBWBWBBWBBBBWWBWBWBWBBWWBBWWBBBWWWB", "WWBBBBWWWWWBWWWBWBWBWWWWBWWWBWBWBWWWWWBBWWBWWBBWBB", "BWWWWBBBWBBWBBBBWWWWWWBBBWWWBBBWWBBBBWBBBWWBBWWWWB", "BBBBWBBWBWBWBBBBBWBBBBWBWBWWBWWBBBWBBWBWWBBBBWWBBB", "WBWWWWWWWWWWBWBWBWBWWWWBWBBWBBBBBWBBBBBBBWBWBWBWBB", "WWWBWWBWBWWBWWBWWBWBWWWBWWBWWBWWWWWBBWWWBBWBWBBBBW", "BBBWBWWBBBWBWWBBBBBWWWBBBBWWWBWBBWWBBWBWWBBWWBBBBB", "WWWWBBWBBBBWWBWWBWBBWBBBWBBWBWWBWBWWWWWWBBBBBWBWBB", "WWWBWWWWWBWBBWWBWWWWWBWWWWBWWWWBBWBBWWBWBWBWBBBWWB", "WBBBWBBWBBWBWBBBBBWBBBWBBBWWWWBWWWBBWWBBBBWBWWBBWW", "BWWWBBBBBWWBBWWBWWBWBBWBWBWBBBWBWWWBBWWBWBWWWBWBWW", "BBBBWBBWBWWBWBBBBWBWBBWBWBWBWWWBBWWWWBBBBWWBWBWBBW", "BBWBBWBBWBWBWBBWBWWBBBWBWWBBBWBBBWWWBWWBWWWBBWBBBW", "BWWBWBWBWWWBBBWBBBWBWBBBBBBWBBBWWWWWWBBBBBWBWBBWBB", "BBBWWBWWBBWBBWBBWBBWBWBWWBWWBWWBWWBWBWWWBWWBWWBWBB", "WWWWWBWWBWBBBWBBWBBWBWBBWWBBWWBWWBWWWWBBBBWBBWWWBB", "BWWWBBWWWBBWWBBWWBWWBWWWBBWWWWWBBWWBWBWWBWBWBBWWBW", "WBWBBBWWBBBBBBWWBWBWBWWWWWBBBWBBWBBBWWWBBBWBWWWBBB", "WBBWWWWWBWWBWBBWWBBWBBWWBWBWWBBWWWBWWWWBBWBWWBBBBB", "WWWWWWWBWBBBWWWBBWWWWWBBBBBWBBWBWWBBBBWWWWWWWBWBBB", "BBWBBBBBWWBBBWWBBWWWWWWWBBBBBWBBWBBBBBBWWBBWBWBBWW", "WBBWBWWBWWBBWBWWBBWWBWWBBWWBWBWWBBBBBBBBBBWWWWBWBB", "WBBWBWBWBWBBBWBBBBWWWBBWWBBWBWWWWBBWWBWBBWBWWWBWBW", "BBBBBBWBBWWBWWBBWBWBWBWBWWBBWWBWBWWWBBBBWBWWBWWWWW", "WWWBWBBWBWBBWBWBWBBWWBBBWWWBBWWBWWBBBWWWWWBBBWWWBB", "BBBWBWBWBBWWBBBBBBBBWBWBWWBBBWBBBWWWWWWWBBWWWWWWWB", "BWWWBBBWWBWBBBWBBWBBWBBWWWWWBBBBWWBBBBBBBBBBWWBBWB", "WWBBBWWBBWBWWWBBBWBBBWBBWBWWWBWBWWBBBBWWWBBWWBBBWB", "WWBWBBBBWBBBWBWBWBWWWWBBWWWWWWBWBBBBBWBBWWWWWWWBWB", "WWWBBWBBBBBBWBBWBWBWBBWWBWWWWBBWBBBBBBBBBWWWBBWBWW", "WBWBWWBWWWBBWWWBBWWWBWWBBWWWWBWBBBBWWBWWBWBBWWWBWW", "WBWWBBBWBBBBBWWWWBBBWWBWBBBWBWBWWBWWWWWBWWBWWWBWWW", "BBWWBBBWWWWWWWWBBBWWWBBWBWWWBWWBWBWWWWBBWBBWWWWBWW", "WWBWWWWBWWWWBBWBBWBWWBWWWBBBBWBWWWBWBWWWWWWBWBBWWW", "BBWBWWBBWBWWWWBBWWBWBWWWBWBBBWWWBWBWBBBWWBBWWBWBWB", "WWBBBWBWBWBBBBBBWBWBBBWBBWWBBBBWBBBBBWWBWBWBWWWWWW", "BWBWWBBWBWBWBBBWBBBWWWBWWBBWWWWWBBBWBWWBBBBWBBWWWW", "WWWBBBBWBWBBBWWBWBBBBWBBBBWBBBBBBBWBBWWWBBWWBBBWWB", "BBBBBWWBBWBBWWBWWWBBBWBBBWBBBBWWWBBBWBBWWWWWBWWWWW", "WBWBBWBBWWWBWWBWWBWBWBBBWWWBBBWWWBWBWBWBWBBBBBBWWB"};
	TEST(convertEx(test, SIZEOFSTRINGARRAY(test)), 145, 777);
}

int main()
{
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();
	Test6();
	Test7();
	cout<<"success";

	getchar();
	return 0;
}