CF 265B(行道树简化版)

B. Roadside Trees (Simplified Edition)

time limit per test

memory limit per test

input

output

n 棵树，编号 1 到 n ，树顶有nuts.第 i 棵树高 h_i. Liss 想吃所有的 nuts.

1的地方. Liss 做下列任意一件事情耗时1s:

• 向树的上方或下方移动1格.
• 吃树顶的 nut .
• 向东边那棵树跳(不能向西跳),高度不变，注意Liss不能从高的地方往低跳。

算出Liss吃掉所有nuts最短时间.

Input

n (1  ≤  n ≤ 10⁵) .

h_i (1 ≤ h_i ≤ 10⁴) .

Output

算出Liss吃掉所有nuts最短时间.

Sample test(s)

input

2 1 2

output

5

input

5 2 1 2 1 1

output

14

注意不能往西跳（一开始以为可以，看题仔细啊！）

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
#define MAXHi (10000+10)
int n,h[MAXN];
int main()
{
  cin>>n;
  for (int i=1;i<=n;i++) cin>>h[i];h[0]=1;
  int ans=0;
  for (int i=1;i<=n;i++) ans+=abs(h[i]-h[i-1]);
/*
  int hmin=h[n];
  for (int i=n-1;i>=1;i--)
  {
    ans=min(ans,ans-abs(h[i]-h[i-1])-abs(h[i+1]-h[i])+abs(h[i-1]-h[i+1])+n-i+abs(hmin-h[i])+abs(hmin-h[n]));    
  }
*/
  ans+=2*n;
  cout<<ans<<endl;
  return 0;
}