程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 545CWoodcutters (貪心orDP)

CodeForces 545CWoodcutters (貪心orDP)

編輯:C++入門知識

CodeForces 545CWoodcutters (貪心orDP)


 

【題目大意】:

有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

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved