「日常训练」Woodcutters（Codeforces Round 303 Div.2 C）

这题惨遭被卡。。卡了一个小时，太真实了。

题意与分析 （Codeforces 545C）

题意：给定\(n\)棵树，在\(x\)位置，高为\(h\)，然后可以左倒右倒，然后倒下去会占据\([x-h,x]\)或者\([x,x+h]\)区间，如果不砍伐，占据\([x,x]\)区域。

问你最多砍多少棵树，砍树的条件是倒下去后占有的区间不能被其他树占据。

分析：在这条题目的条件下，这是一个傻逼贪心题。（然后我读错两次题目，怎么也想不出来贪心策略。。。。）

很简单的策略：能往左倒往左倒，能往右倒往右倒。因为树的倒下无论如何只会影响额外的一棵树！！（换句话说，如果说倒下的区间不用考虑树的存在，就很有意思了）举个例子，考虑一种极端情况：第\(i\)棵树到第\(n\)棵树如果挨个往左倒正好完美覆盖。那么这种情况下你第\(i-1\)棵树如果可以往右倒照样可以往右倒，因为每棵树的倒下只影响另外左右一个树，那么我大不了第\(i\)棵树不倒，我的答案不会更差。这样就确定了贪心策略的正确性。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (repType i = (a); i <= (b); ++i)

#define per(i, a, b) for (repType i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll=long long;

using repType=int;

int main()

{

	int n; cin>>n;

	pair<int,int> tree[100005];

	rep(i,1,n) cin>>tree[i].fi>>tree[i].se;

	int cnt=0;

	int npos=0,ntree=1;

	int cut[100005]; ZERO(cut);

	rep(i,1,n)

	{

		int l_boundary=tree[i].fi-tree[i].se,

			r_boundary=tree[i].fi+tree[i].se;

		bool lok=true;

		per(j,i-1,1)

		{

			if(tree[j].fi>=l_boundary || (cut[j]==2&&tree[j].fi+tree[j].se>=l_boundary))

			{

				lok=false; break;

			}

			if(tree[j].fi+tree[j].se<l_boundary) break;

		}

		if(lok) { cut[i]=1; continue; }

		bool rok=true;

		rep(j,i+1,n)

		{

			if(tree[j].fi>r_boundary) break;

			else if(tree[j].fi<=r_boundary) {rok=false; break;}

		}

		if(rok) cut[i]=2;

	}

	int ans=0;

	rep(i,1,n) if(cut[i]) ans++;

	cout<<ans<<endl;

	return 0;

}