题意

给定一个长度为 n 的数组。要求相临的数大小不相同，假如相临数的相同，
你可以通过将 a[i]+1 来改变它的大小，但是需要付出 b[i]的代价，同时对于每
个 a[i]只能加一次。问你付出的最小代价。

输入描述

第 1 行 1 个整数 n，表示数组长度为 n
接下来 n 行，每行 2 个正整数 a[i]与 b[i]，表示 a 数组中的第 i 个数，以及将第 i 个数+1 的代价。
对于20%的数据，保证b[i] = 1
对于另外10%的数据，保证所有a[i]相等
对于另外10%的数据，保证所有的a[i]不相等
对于100%的数据，1<=n<=2e5，0<=a[i]、b[i]<=1e9

输出描述

1 行，一个数字 ans，表示最小代价。

题意

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5;
int a[MAXN],b[MAXN];
int main(void) {
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i]>>b[i];
    }
    int l = 1, r = 2, ans = 0;
    while (l <= n) {
        while (r <= n && a[l] == a[r]) r++;
        if (r - l > 1) {
            int sum1 = 0;
            for (int j = l; j < r; j += 2) sum1 += b[j];
            int sum2 = 0;
            for (int j = l + 1; j < r; j += 2) sum2 += b[j];
            ans += min(sum1, sum2);
        }
        l = r; r++;
    }
    cout<<ans<<endl;
    return 0;
}

但是我们要正确的做出这个题目我们要考虑几个地方：

1，当连续个a相同的连在一起时，我们要考虑是选择哪些进行加一，就是说我现在的a都相同，那么我们就考虑是选择还是进行加一。

2，当出现阶梯状的时，要如何处理，举个例子，这里如果我们加一了，那么这个时候和相同，那么必定要加一。

考虑到上面情况，我能想到的做法就是使用dp，设dp[n][2]，dp[i][0]表示第i个不加一,dp[i][1]表示第i个加一。

转移方程有：

if (a[i] != a[i - 1]) dp[i][0] = min(dp[i][0], dp[i - 1][0]);
if (a[i] != (a[i - 1] + 1)) dp[i][0] = min(dp[i][0], dp[i - 1][1]);
if ((a[i] + 1) != a[i - 1]) dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i]);
if ((a[i] + 1) != (a[i - 1] + 1)) dp[i][1] = min(dp[i][1], dp[i - 1][1] + b[i]);

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n,a[maxn],b[maxn];
#define INF 1e18
ll dp[maxn][2];
int main(void) {
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    for(int i = 1 ; i <= n ; ++i){
        cin>>a[i]>>b[i];
        dp[i][0] = dp[i][1] = INF;
    }
    dp[1][0] = 0; dp[1][1] = b[1];
    for(int i = 2; i <= n ; ++i) {
        if (a[i] != a[i - 1]) dp[i][0] = min(dp[i][0], dp[i - 1][0]);
        if (a[i] != (a[i - 1] + 1)) dp[i][0] = min(dp[i][0], dp[i - 1][1]);
        if ((a[i] + 1) != a[i - 1]) dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i]);
        if ((a[i] + 1) != (a[i - 1] + 1)) dp[i][1] = min(dp[i][1], dp[i - 1][1] + b[i]);
    }
    ll ans = min(dp[n][0],dp[n][1]);
    cout << ans << endl;
    return 0;
}