Frog 1
题面翻译
N N N 个石头，编号为 1 , 2 , . . . , N 1,2,...,N 1,2,...,N。对于每个 i ( 1 ≤ i ≤ N ) i(1 \leq i \leq N) i(1≤i≤N)，石头 i i i 的高度为 h i h_i hi。
最初有一只青蛙在石头 1 1 1 上。他将重复几次以下操作以到达石头 N N N：
- 如果青蛙当前在石头 i i i 上，则跳到石头 i + 1 i+1 i+1 或石头 i + 2 i+2 i+2。需要 ∣ h i − h j ∣ |h_i - h_j| ∣hi−hj∣ 的费用，而 j j j 是要落到上面的石头。
找到青蛙到达石头 N N N 之前需要的最小总费用。
题目描述
$ N $ 個の足場があります。 足場には $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、足場 $ i $ の高さは $ h_i $ です。
最初、足場 $ 1 $ にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 $ N $ まで辿り着こうとしています。
- 足場 $ i $ にいるとき、足場 $ i\ +\ 1 $ または $ i\ +\ 2 $ へジャンプする。 このとき、ジャンプ先の足場を $ j $ とすると、コスト $ |h_i\ -\ h_j| $ を支払う。
カエルが足場 $ N $ に辿り着くまでに支払うコストの総和の最小値を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ h_1 $ $ h_2 $ $ \ldots $ $ h_N $
输出格式
カエルが支払うコストの総和の最小値を出力せよ。
样例 #1
样例输入 #1
4
10 30 40 20
样例输出 #1
30
样例 #2
样例输入 #2
2
10 10
样例输出 #2
0
样例 #3
样例输入 #3
6
30 10 60 10 60 50
样例输出 #3
40
提示
制約
- 入力はすべて整数である。
- $ 2\ \leq\ N\ \leq\ 10^5 $
- $ 1\ \leq\ h_i\ \leq\ 10^4 $
Sample Explanation 1
足場 $ 1 $ → $ 2 $ → $ 4 $ と移動すると、コストの総和は $ |10\ -\ 30|\ +\ |30\ -\ 20|\ =\ 30 $ となります。
Sample Explanation 2
足場 $ 1 $ → $ 2 $ と移動すると、コストの総和は $ |10\ -\ 10|\ =\ 0 $ となります。
Sample Explanation 3
足場 $ 1 $ → $ 3 $ → $ 5 $ → $ 6 $ と移動すると、コストの総和は $ |30\ -\ 60|\ +\ |60\ -\ 60|\ +\ |60\ -\ 50|\ =\ 40 $ となります。
#include<bits/stdc++.h>
using namespace std;
inline int read();
long long i,q,w,e,r,t,y,u,o,p,s,d,f,g,h,j,l,z,x,c,v,n,m,k;
long long a[1100][1100],b[111100],ss[111100];
long long asd[10000][10000];
int main()
{
ios::sync_with_stdio(false); cout.tie(0); cin.tie(0);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>b[i];
}
ss[1]=0;
ss[2]=abs(b[1]-b[2]);
for(i=3;i<=n;i++)
{
ss[i]=min(ss[i-1]+abs(b[i]-b[i-1]),ss[i-2]+abs(b[i]-b[i-2]));
}
cout<<ss[n];
return 0;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}