# 14174: 【原4174】fuji

### 题目描述

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

## Description

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

## Sample Input

5 1 2 7 4 10 4 5 2 5 2

## Sample Output

``````3
``````

## 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;
}
``````