14174: 【原4174】fuji

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4174

Description

“樱花开了几转，东京之旅一早比一世遥远。”

小L同学去富士山游玩，一天的游览结束之后，她准备回东京，然而路上有许许多多的高大的山峰，车辆无法通过。她获得了一种超能力，可以把一座山推倒。她想要推倒尽可能多的山峰，并且为了保证美观，她希望所有的山峰没有交点。可是她手边没有电脑，不知道要推倒多少山峰，现在请你来帮忙解决这个问题。

给出$n$座山峰的位置$x_i$和高度$h_i$，每推倒一座山峰会覆盖坐标轴上[$x_i-h_i,x_i$]或者[$x_i,x_i+h_i$]的区域，区域包括两个端点。没有推倒的山峰仅覆盖$x_i$一点。在覆盖区域没有交点的情况下，最多能推倒多少山峰？

Input Format

输入共三行，第一行包含一个正整数$n$，表示山峰的数目；

第二行包含$n$个正整数$x_i$，表示第$i$座山峰的位置；

第三行包含$n$个正整数$h_i$，表示第$i$座山峰的高度。

Output Format

输出共一行，包含一个整数，表示最多可推倒的山峰数目。

Sample Input

5 1 2 7 4 10 4 5 2 5 2

Sample Output

3

数据规模与约定

对于$70\%$的数据，$1\le n\le 20$；

对于$100\%$的数据，$1\le n \le 10^5$，$1\le x_i, h_i \le 10^{18}$，保证$x_i$两两不同。

ligongzzz's solution

#include "iostream"
#include "algorithm"
#include "cstdio"
#include "cstring"
using namespace std;

class mountain {
public:
    long long pos = 0;
    long long height = 0;
};

//山峰的位置
long long pos[100009] = { 0 };
long long height[100009] = { 0 };
mountain mountains[100009];

//保存DP数据
int dp_temp[100009][2];

//保存数量
int num = 0;

//动态规划
int dp(int cur_pos, int cur_state) {
    if (cur_pos >= num)
        return 0;
    if (dp_temp[cur_pos][cur_state] >= 0)
        return dp_temp[cur_pos][cur_state];
    //判断是否可以往左边推
    if (cur_pos == 0 || (cur_state == 0 && pos[cur_pos] - height[cur_pos] > pos[cur_pos - 1]) ||
        (cur_state == 1 && pos[cur_pos] - height[cur_pos] > pos[cur_pos - 1] + height[cur_pos - 1])) {
        int ans = 1 + dp(cur_pos + 1, 0);
        dp_temp[cur_pos][cur_state] = ans;
        return ans;
    }
    else {
        int ans = 0;
        //判断是否可以往右推
        if (cur_pos == num - 1 || pos[cur_pos] + height[cur_pos] < pos[cur_pos + 1]) {
            ans = 1 + dp(cur_pos + 1, 1);
        }
        //不推
        int shit_ans = dp(cur_pos + 1, 0);
        ans = shit_ans > ans ? shit_ans : ans;
        dp_temp[cur_pos][cur_state] = ans;
        return ans;
    }
}

int main() {
    scanf("%d", &num);

    memset(dp_temp, -1, sizeof(dp_temp));

    for (int i = 0; i < num; ++i)
        scanf("%lld", &mountains[i].pos);
    for (int i = 0; i < num; ++i)
        scanf("%lld", &mountains[i].height);

    //排序
    sort(mountains, mountains + num, [](mountain a, mountain b) {
        return a.pos < b.pos;
    });

    //写入
    for (int i = 0; i < num; ++i) {
        pos[i] = mountains[i].pos;
        height[i] = mountains[i].height;
    }

    printf("%d", dp(0, 0));

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

struct M {
    long long pos;
    long long height;

    M() : pos(0), height(0) {}

    M(long long a, long long b) : pos(a), height(b) {}

    M operator=(M &right) {
        if (&right != this) {
            this->pos = right.pos;
            this->height = right.height;
        }

        return *this;
    }

    M(const M &right) {
        this->pos = right.pos;
        this->height = right.height;
    }
};

void qSort(M *nums, int l, int h) {
    if (l >= h) {
        return;
    }
    int first = l, last = h;
    M key(nums[first]);

    while (first < last) {
        while (first < last && nums[last].pos >= key.pos) {
            --last;
        }
        nums[first] = nums[last];
        while (first < last && nums[first].pos <= key.pos) {
            ++first;
        }
        nums[last] = nums[first];
    }
    nums[first] = key;
    qSort(nums, l, first - 1);
    qSort(nums, first + 1, h);
}

M mountain[maxN] = {};
int n, sum = 0;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        long long p;
        cin >> p;
        mountain[i].pos = p;
    }
    for (int i = 1; i <= n; i++) {
        long long h;
        cin >> h;
        mountain[i].height = h;
    }
    if (n == 1) {
        cout << 1;
        return 0;
    } else if (n == 2) {
        cout << 2;
        return 0;
    }

    qSort(mountain, 1, n);

    for (int i = 2; i < n; i++) {
        if (mountain[i].pos - mountain[i].height > mountain[i - 1].pos) {
            sum++;
        } else if (mountain[i].pos + mountain[i].height < mountain[i + 1].pos) {
            mountain[i].pos += mountain[i].height;
            sum++;
        }
    }
    sum += 2;

    cout << sum;

    return 0;
}