gistfile1.txt

#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
using INPUT_TYPE = vector<vector<unsigned char>>;
using CONVERTED_TYPE = vector<unsigned int>;
using OUTPUT_TYPE = vector<pair<size_t, size_t>>;
// 数据按行转换成十进制数组，O(M*N)
CONVERTED_TYPE convert(const INPUT_TYPE &input, size_t m, size_t n);
// 如果要求序列是连续的，O(M*M)，这个做法是低效的
OUTPUT_TYPE cont(const CONVERTED_TYPE &in, int lines, int columns);
// 输出
void output(const OUTPUT_TYPE &out, const INPUT_TYPE &input);
// 如果序列可以不连续，即背包问题，O（M*columns)
vector<bool> discont(const CONVERTED_TYPE &in, int lines, int columns);
int main(int argc, char const *argv[])
{
	// input
	const size_t m = 5, n = 6;
	const int lines = 2, columns = 3;
	INPUT_TYPE input = {
		{ 0,1,1,0,0,0 },
		{ 0,1,0,1,0,0 },
		{ 0,1,1,1,0,0 },
		{ 1,1,0,0,1,1 },
		{ 0,1,0,0,0,0 }
	};
	auto converted = convert(input, m, n);
	auto result = cont(converted, lines, columns);
	cout << "cont:" << endl;
	output(result, input);
	cout << "discont:" << endl;
	auto result2 = discont(converted, lines, columns);
	for (size_t i = 0; i < m; i++)
	{
		if (result2[i])
		{
			stringstream ss;
			ss << "[";
			for (auto k : input[i])
			{
				ss << (int)k << ",";
			}
			ss << "]";
			cout << ss.str() << endl;
		}
	}
	cin.get();

	return 0;
}
CONVERTED_TYPE convert(const INPUT_TYPE &input, size_t m, size_t n)
{
	assert(m == input.size());
	CONVERTED_TYPE converted(m, 0);
	for (size_t i = 0; i < m; i++)
	{
		assert(n == input[i].size());
		for (size_t j = 0; j < n; j++)
		{
			converted[i] = converted[i] * 2 + input[i][j];
		}
	}
	return converted;
}
OUTPUT_TYPE cont(const CONVERTED_TYPE &in, int lines, int columns)
{
	OUTPUT_TYPE result;
	size_t m = in.size();
	for (size_t i = 0; i < m; i++)
	{
		vector<unsigned int> dp(m, 0);
		for (size_t j = i; j < m; j++)
		{
			dp[j] = j == i ? in[j] : (dp[j - 1] | in[j]);
			int count1 = _mm_popcnt_u32(dp[j]);
			if (count1 > columns)
			{
				break;
			}
			if (count1 <= columns && ((j - i + 1) > lines))
			{
				result.push_back(make_pair(i, j));
			}
		}
	}

	return result;
}
void output(const OUTPUT_TYPE &out, const INPUT_TYPE &input)
{
	for (size_t i = 0; i < out.size(); i++)
	{
		stringstream ss;
		ss << "OUTPUT " << i + 1 << endl;
		for (size_t j = out[i].first; j <= out[i].second; j++)
		{
			ss << "[";
			for (auto k : input[j])
			{
				ss << (int)k << ",";
			}
			ss << "]" << endl;
		}
		cout << ss.str() << endl;
	}
}
vector<bool> discont(const CONVERTED_TYPE &in, int lines, int columns)
{
	size_t m = in.size();
	vector<vector<int>> dp(m + 1);
	vector<vector<unsigned int>> tmpValue(m + 1);
	for (auto &i : dp)
	{
		i.resize(columns + 1, 0);
	}
	for (auto &i : tmpValue)
	{
		i.resize(columns + 1, 0);
	}
	for (size_t i = 1; i <= m; i++)
	{
		for (size_t j = 1; j <= columns; j++)
		{
			unsigned int w = _mm_popcnt_u32(in[i - 1] | tmpValue[i - 1][j]) - _mm_popcnt_u32(tmpValue[i - 1][j]);
			if (w <= j && dp[i - 1][j - w] + 1 > dp[i - 1][j])
			{
				dp[i][j] = dp[i - 1][j - w] + 1;
				tmpValue[i][j] = in[i - 1] | tmpValue[i - 1][j];
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
				tmpValue[i][j] = tmpValue[i - 1][j];
			}
		}
	}
	vector<bool> result(m, false);
	if (dp[m][columns] <= lines)
	{
		return result;
	}
	for (size_t i = m, j = columns; i > 0; i--)
	{
		if (dp[i][j] > dp[i - 1][j])
		{
			result[i - 1] = true;
			unsigned int w = _mm_popcnt_u32(tmpValue[i][j]) - _mm_popcnt_u32(tmpValue[i - 1][j]);
			j = j - w;
		}
	}
	return result;
}