当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,