Code Forces 448C Painting Fence 贪婪的递归

略有上升称号，最近有很多问题，弥补啊，各类竞赛滥用，来不及做出了所有的冠军。这个话题这是一个长期记忆的主题。这是不是太困难，基本技能更灵活的测试，每次我们来看看这个问题可以被删除，处理然后分段层，贪婪的想法画一幅画，可以发现，下一步骤是如何应用，搜递归就能够了。当时写错了。还是漏了一些，如今补题才发现，长记性咯

http://codeforces.com/contest/448/problem/C

#include<iostream>

#include<cstdio>

#include<list>

#include<algorithm>

#include<cstring>

#include<string>

#include<queue>

#include<stack>

#include<map>

#include<vector>

#include<cmath>

#include<memory.h>

#include<set>

#define ll long long

#define eps 1e-8

const int inf = 0xfffffff;

const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;

//typedef pair<int,int > P;

//vector<pair<int,int> > ::iterator iter;

//

//map<ll,int >mp;

//map<ll,int >::iterator p;

int dfs(vector<int > G) {

	int minn = inf;

	int len = G.size();

	for(int i=0;i<G.size();i++)

		minn = min(G[i],minn);

	if(minn > len)return len;//这样横着来不如竖着来

	for(int i=0;i<G.size();i++)

		G[i] -= minn;

	int ans = minn;

	vector<int > now;

	for(int i=0;i<G.size();i++) {

		if(G[i])

			now.push_back(G[i]);

		else {

			ans += dfs(now);

			now.clear();

		}

	}

	if(now.size())

		ans += dfs(now);

	ans = min(len,ans);

	return ans;

}

int main() {

	int n;

	while(scanf("%d",&n) == 1) {

		vector<int > G;

		for(int i=0;i<n;i++) {

			int x;

			scanf("%d",&x);

			G.push_back(x);

		}

		int ans = dfs(G);

		printf("%d\n",ans);

	}

	return 0;

}

秒客网

Code Forces 448C Painting Fence 贪婪的递归

相关文章