博客

不平衡数组

链接：https://ac.nowcoder.com/acm/contest/5881/C

来源：牛客网

不平衡数组

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

给定一个长度为 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，表示最小代价。

示例1

输入

复制

4

1 2

2 2

2 3

4 1

输出

复制

2

分析：这题一看就是动态规划，怎么说呐，因为前后的状态相互影响，那么动态规划是比较好求这类的。

考虑状态数组，既然是考虑加1与不加1的最小代价，

那么我们就根据dp[i][0/1]表示当前i个相邻不相等的加1与不加1的最小代价

我们总共有四种情况.

情况一：如果a[i-1]=a[i],

如果第i位不加1，那么i-1位就必需加

转移方程就是dp[i][0]=dp[i-1][1]

如果第i位加1，那么i-1位就不能加1

那么 dp[i][1]=dp[i-1][0]+b[i] //加1就需要加上代价

情况二：如果a[i-1]+1=a[i],

如果第i位不加1，那么i-1位就不能加1

dp[i][0]=dp[i-1][0];

如果第i位加1，那么i-1位可以加1，也可以不加1，因为加1也比i位小；所以我们只需要选择i-1位加1与不加1代价最小的就是了

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

情况三：如果a[i-1]-1=a[i],

如果第i位不加1，那么i-1位就加1与不加1都比第i位大，所以同样选择加1与不加1代价最小的就是了

dp[i-1][0]=min(dp[i-1][0],dp[i-1][1]);

如果第i位加1，那么i-1位就必需加1，才能保证彼此不相等；

dp[i][1]=dp[i-1][1]+b[i];

情况四：那么就是a[i-1]与a[i]相差大于1了，

如果第i位不加1，那么第i-1位加一与不加一对其没有影响，那么我们只需要选择最小的代价就是了

dp[i][0]=min(dp[i-1][1],dp[i-1][0]);

如果第i位加1，道理一样，i-1加不加无所谓，

dp[i][1]=min(dp[i-1][1],dp[i-1][0]);

最终结果就是第n位加1与不加1的最小值了

初始化dp[i][1]=dp[i][0]=0;表示只有一位，肯定不加，代价最小，那么就是0；

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 1329103910
typedef long long ll;
const ll mod=1e9+7;
const ll N=3e5+5;
const double eps=1e-7;
using namespace std;
ll a[N],b[N];
ll dp[N][2];//考虑两种状态即使+1或者不+1对其的影响
int main()
{
        ios;
        ll n,t;
        cin>>n;
        for(ll i=1;i<=n;i++) dp[i][0]=0,dp[i][1]=0;
        for(ll i=1;i<=n;i++) cin>>a[i]>>b[i];
        for(ll i=1;i<=n;i++)
        {
            if(a[i-1]==a[i])
            {
                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][0],dp[i-1][1]);
                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][0],dp[i-1][1])+b[i];
            }
        }
        cout<<min(dp[n][0],dp[n][1]);
        return 0;
}