CF 265B(行道树简化版)
B. Roadside Trees (Simplified Edition)
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output
从西向东有 n 棵树,编号 1 到 n ,树顶有nuts.第 i 棵树高 hi. Liss 想吃所有的 nuts.
Liss 在第1棵树的高度为1的地方. Liss 做下列任意一件事情耗时1s:
向树的上方或下方移动1格.
吃树顶的 nut .
向东边那棵树跳(不能向西跳),高度不变,注意Liss不能从高的地方往低跳。
算出Liss吃掉所有nuts最短时间.
Input
第一行为 n (1 ≤ n ≤ 105) .
接下来n行为序列 hi (1 ≤ hi ≤ 104) .
Output
算出Liss吃掉所有nuts最短时间.
Sample test(s)
input
2
1
2
output
5
input
5
2
1
2
1
1
output
14
注意不能往西跳(一开始以为可以,看题仔细啊!)
[cpp]
#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()
{ www.zzzyk.com
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;
}
补充:软件开发 , C++ ,