刷栏杆Painting Fence(贪心|分治)

Problem - 448c - Codeforces

最开始的想法：每次迭代都进行一次刷栏杆的操作，贪心选择目的为刷到更多块，因此对比横刷和竖刷一次能刷的块个数。接着对如果栏杆底部出现分隔（不再连续）则分治。此做法部分正确，贪心选择结果不是全局最优解。

#include<iostream>
#include<vector>
using namespace std;

bool isEmpty(vector<int>h, int left, int right) {
	for (int i = left; i <= right; i++)
		if (h[i] > 0) return 0;
	return 1;
}

//{lenth,left,right}
vector<int> findMaxRaw(vector<int> h, int left, int right) {
	int i = left;
	while (h[i] <= 0) i++;
	vector<int> result{ 1,i,i };
	for (int j = i+1; j <= right; j++) {
		if (h[j] <= 0) break;
		else {
			if (j - i + 1 > result[0]) {
				result[0] = j - i + 1;
				result[1] = i;
				result[2] = j;
			}
		}
	}
	return result;
}

int solution(vector<int> h, int left, int right) {
	if (isEmpty(h, left, right)) return 0;
	vector<int> maxraw=findMaxRaw(h, left, right);
	vector<int> maxcol{ 0,-1 };
	//handle
	for(int i=left;i<=right;i++)
		if (h[i] > maxcol[0]) {
			maxcol[0] = h[i];
			maxcol[1] = i;
		}
	if (maxraw[0] >= maxcol[0])
		for (int i = maxraw[1]; i <= maxraw[2]; i++) h[i]--;
	else h[maxcol[1]] = 0;
	//split and solve
	int i = left;
	while (i<=right && h[i] <= 0) i++;
	int j = i;
	int sum = 1;
	while (i<=right && j <= right) {
		if (j == right) {
			sum += solution(h, i, j);
			break;
		}
		if (h[j + 1] <= 0) {
			sum += solution(h, i, j);
			i = j + 1;
			while (i <= right && h[i] <= 0) i++;
			j = i;
		}
		else j++;
	}
	return sum;
}


int main() {
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++) cin >> h[i];
	cout << solution(h, 0, h.size() - 1);
	return 0;
}

正确做法：每次迭代选择若干次横刷或者若干次竖刷。贪心选择是本次迭代进行的最少刷栏杆次数。横刷则先从底部刷至出现分隔，分治。竖刷则次数为本次迭代栏杆数。

#include<iostream>
#include<vector>
using namespace std;

bool isEmpty(vector<int>h, int left, int right) {
	for (int i = left; i <= right; i++)
		if (h[i] > 0) return 0;
	return 1;
}

int findmin(vector<int> h, int left, int right) {
	int min = h[left];
	for (int i = left + 1; i <= right; i++)
		if (h[i] < min) min = h[i];
	return min;
}

int solution(vector<int> h, int left, int right) {
	if (left>right||isEmpty(h, left, right)) return 0;
	if (left == right) return 1;
	//vector<int> maxraw=findMaxRaw(h, left, right);
	//vector<int> maxcol{ 0,-1 };
	////handle
	//for(int i=left;i<=right;i++)
	//	if (h[i] > maxcol[0]) {
	//		maxcol[0] = h[i];
	//		maxcol[1] = i;
	//	}
	//if (maxraw[0] >= maxcol[0])
	//	for (int i = maxraw[1]; i <= maxraw[2]; i++) h[i]--;
	//else h[maxcol[1]] = 0;

	int sum = 0;
	int row = findmin(h, left, right);
	for (int i = left; i <= right; i++) h[i]-=row;
	sum += row;

	//split and solve
	int i = left;
	while (i<=right && h[i] <= 0) i++;
	int j = i;
	while (i<=right && j <= right) {
		if (j == right) {
			sum += solution(h, i, j);
			break;
		}
		if (h[j + 1] <= 0) {
			sum += solution(h, i, j);
			i = j + 1;
			while (i <= right && h[i] <= 0) i++;
			j = i;
		}
		else j++;
	}
	if (sum <= right - left + 1) return sum;
	else return right - left + 1;
}


int main() {
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++) cin >> h[i];
	cout << solution(h, 0, h.size() - 1);
}