首页 > 其他 > 详细

CF545C Woodcutters

时间:2021-05-07 14:57:53      阅读:27      评论:0      收藏:0      [点我收藏+]

原题链接

  • 题意:一棵树,有高度,在一维平面上,可以向左向右砍到,不允许重叠,然后求最大砍倒树的数量。
  • 题解:从左往右的话,就现往左倒,如果不可以往左倒,就往右倒。
  • 代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
struct node {
    ll pos, h, l, r;
}p[N];
int dp[N][4];
int main() {
    int n;cin >> n;
    for (int i = 1; i <= n ;i ++) {
        cin >> p[i].pos >> p[i].h;
        p[i].l = p[i].pos - p[i].h;
        p[i].r = p[i].pos + p[i].h;
    }
    int now = 0;
    for (int i = 1; i <= n; i ++) {
        if (i == 1 || i == n){
            now++;
            continue;
        }
        if (p[i].l > p[i-1].pos) {
            now++;
        } else {
            if (p[i].r < p[i + 1].pos) {
                now++;
                p[i].pos = p[i].r;
            }
        }
    }
    cout << now << endl;
    return 0;
}

CF545C Woodcutters

原文:https://www.cnblogs.com/Xiao-yan/p/14738643.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!