表示,dp的魅力;
只要知道这题用dp做,就差不多了;怎么想到dp?一方面做题多,另一方面排除法,别的都不行。
这道题求最小值,最值一般dp。二分,贪心。
最后选dp;
dp[][0/1]表示,到达i的时候,前i-1个数满足题意,第i个数是否需要+/-1;
需要判断a[i]与a[i-1]的关系;

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=300000;
ll a[maxn],b[maxn],dp[maxn][2];
int main()
{
    ll n,ans=0,ok=0;
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i]>>b[i];
    }
    for(ll i=1;i<=n;i++)
    {
        if(a[i]==a[i-1])
        {
            dp[i][0]=dp[i-1][1];
            dp[i][1]=dp[i-1][0]+b[i];
        }
        else if(a[i-1]+1==a[i])
        {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+b[i];
        }
        else if(a[i-1]==a[i]+1)
        {
            dp[i][0]=min(dp[i-1][1],dp[i-1][0]);
            dp[i][1]=dp[i-1][1]+b[i];
        }
        else {
            dp[i][0]=min(dp[i-1][1],dp[i-1][0]);
            dp[i][1]=min(dp[i-1][1],dp[i-1][0])+b[i];
        }
    }
    cout<<min(dp[n][1],dp[n][0]);
}