宝贝，生日快乐！！！LevOJ P1779 小胡同学的跳板

思路：

动力小子是吧 ੭ ᐕ)੭*⁾⁾

用 dp[i] 存储经过第i块跳板后所能到达的最远距离, pos[i] 存储第i块跳板的位置， jump[i] 存储第i块跳板的跳跃距离。

对于第 i 块跳板：

如果能到达的最远距离小于下一块跳板的距离，即 dp[i]<pos[i] ，则必须要走路。

否则，

如果第i块跳板所能到达的最远距离大于下一块跳板跳跃的最远距离，即 dp[i]>(pos[i+1]+jump[i+1]) ,则直接从第i块跳板跳到最远距离即可。

如果第i块跳板所能到达的最远距离小于等于下一块跳板跳跃的最远距离，即 dp[i]≤(pos[i+1]+jump[i+1]) ,则直接跳到下一块跳板上即可。

最后跳板跳完了检查是否到达终点，没到终点则必须要走路。

AC代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=100010;

int n,m;
int dp[N],pos[N],jump[N];
int ans;

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>pos[i]>>jump[i];
    }
    ans=pos[1];
    dp[1]=pos[1]+jump[1];
    for(int i=1;i<=n;i++){
        if(dp[i]<pos[i+1]){
            ans+=pos[i+1]-dp[i];
            dp[i+1]=pos[i+1]+jump[i+1];
        }else{
            if(dp[i]>(pos[i+1]+jump[i+1])){
                dp[i+1]=dp[i];
            }else{
                dp[i+1]=pos[i+1]+jump[i+1];
            }
        }
    }
    if(m>dp[n]){
        ans+=m-dp[n];
    }
    cout<<ans<<endl;
    return 0;
}