atcoder A - Frog 1（DP）-白红宇

atcoder A - Frog 1（DP）

阅读量：4308 次

发布时间：2019-06-06

本文共 2723 字，大约阅读时间需要 9 分钟。

A - Frog 1

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $100100$ points

Problem Statement

There are $NN$ stones, numbered $1,2,\dots,N1,2,\dots,N$ . For each $ii$ ( $1\leqi\leqN1\leqi\leqN$ ), the height of Stone $ii$ is ${hihi}_{ihi}$ .

There is a frog who is initially on Stone $11$ . He will repeat the following action some number of times to reach Stone $NN$ :

If the frog is currently on Stone $ii$ , jump to Stone $i+1i+1$ or Stone $i+2i+2$ . Here, a cost of $|hi-hj||hi-hj|$ is incurred, where $jj$ is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone $NN$ .

Constraints

All values in input are integers.

$2\leqN\leq1052\leqN\leq105$

$1\leqhi\leq1041\leqhi\leq104$

Input

Input is given from Standard Input in the following format:

NNh1h1 h2h2 …… hNhN

Output

Print the minimum possible total cost incurred.

Sample Input 1 Copy

Copy

410 30 40 20

Sample Output 1 Copy

Copy

If we follow the path $11$ → $22$ → $44$ , the total cost incurred would be $|10-30|+|30-20|=30|10-30|+|30-20|=30$ .

Sample Input 2 Copy

Copy

210 10

Sample Output 2 Copy

Copy

If we follow the path $11$ → $22$ , the total cost incurred would be $|10-10|=0|10-10|=0$ .

Sample Input 3 Copy

Copy

630 10 60 10 60 50

Sample Output 3 Copy

Copy

If we follow the path $11$ → $33$ → $55$ → $66$ , the total cost incurred would be $|30-60|+|60-60|+|60-50|=40|30-60|+|60-60|+|60-50|=40$ .

题目链接：

题意：给你一堆石头，每一个石头有一个高度，有一只青蛙站在第一个石头上，青蛙每一次可以跳1-2个石头，并且产生起跳高度和落地高度的差的消耗。

问你青蛙跳到第N个石头，最小需要消耗多少能量？

思路：

简单的线性DP，定义dp[i]的状态意义为青蛙跳到第i个石头的时候消耗的最小能量，

转移方程即为：dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1]))

初始状态定义： dp[1] = 0 , dp[2]=| a[2]-a[1] |

dp[2]一定要预处理，状态转移只能从i=3开始，因为第二个石头只能由第一个石头跳过去。

不这样定义会wa的。（亲测，23333）

我的AC代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #define rep(i,x,n) for(int i=x;i
                 
                  #define pll pair
                  
                   #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define gg(x) getInt(&x)using namespace std;typedef long long ll;inline void getInt(int* p);const int maxn=1000010;const int inf=0x3f3f3f3f;/*** TEMPLATE CODE * * STARTS HERE ***/ll n;ll dp[maxn];ll a[maxn];int main(){ gbtb; cin>>n; repd(i,1,n) { cin>>a[i]; } dp[1]=0; dp[0]=0; dp[2]=abs(a[2]-a[1]); repd(i,3,n) { dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1])); } cout<
                   
                    = '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } }}