CodeForces 545C Woodcutters （贪心orDP）

CodeForces 545C Woodcutters （贪心orDP）

【题目链接】：​​click here~~​​

【题目大意】：

有n棵树，给出每棵树的位置和高度，然后把树砍掉，树可以向左倒也可以向右倒。输出最多能砍几棵树。  【思路】：利用贪心的思想。第一棵树的左边和最后一棵树的右边没树，所以他们向两边倒，然后对于中间的树来说，首先先向左边倒，然后左边距离如果不够的话再向右边倒，向右倒的时候注意更新一下距离。

代码：

/* * Problem: CodeForces 545C* Running time: 46MS * Complier: G++ * Author: herongwei * Create Time: 7:59 2015/9/17 星期四*/ #include #include #include #include using namespace std;typedef long long LL;const int N=1e5+100;const int inf=0x7f7f7f7f;struct node{ int codx,heg; // coordinate and height bool ck;} arr[N];int main(){ int t,n,m; scanf("%d",&t); for(int i=1; i<=t; ++i){ scanf("%d %d",&arr[i].codx,&arr[i].heg); } arr[0].codx=-inf; // init arr[t+1].codx=inf; int s=0; for(int i=1; i<=t; ++i){ // left if(arr[i].codx-arr[i].heg>arr[i-1].codx){ ++s; continue; } if(arr[i].codx+arr[i].heg

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。