CF-1121D-D. Make The Fence Great Again

D. Make The Fence Great Again

time limit per test：2 seconds memory limit per test：256 megabytes inputstandard input outputstandard output

You have a fence consisting of n vertical boards. The width of each board is 1. The height of the i-th board is ai. You think that the fence is great if there is no pair of adjacent boards having the same height. More formally, the fence is great if and only if for all indices from 2 to n, the condition ai−1≠ai holds.

Unfortunately, it is possible that now your fence is not great. But you can change it! You can increase the length of the i-th board by 1, but you have to pay bi rubles for it. The length of each board can be increased any number of times (possibly, zero).

Calculate the minimum number of rubles you have to spend to make the fence great again!

You have to answer q independent queries.

Input The first line contains one integer q (1≤q≤3⋅105) — the number of queries.

The first line of each query contains one integers n (1≤n≤3⋅105) — the number of boards in the fence.

The following n lines of each query contain the descriptions of the boards. The i-th line contains two integers ai and bi (1≤ai,bi≤109) — the length of the i-th board and the price for increasing it by 1, respectively.

It is guaranteed that sum of all n over all queries not exceed 3⋅105.

It is guaranteed that answer to each query will not exceed 1018.

Output For each query print one integer — the minimum number of rubles you have to spend to make the fence great.

Example input

3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2

outputCopy

2
9
0

Note In the first query you have to increase the length of second board by 2. So your total costs if 2⋅b2=2.

In the second query you have to increase the length of first board by 1 and the length of third board by 1. So your total costs if 1⋅b1+1⋅b3=9.

In the third query the fence is great initially, so you don’t need to spend rubles.

题目大意

一共有 t 次询问，每次有 n 组数据，分别是 ai(表示篱笆的高度) bi(表示每增加一个高度需要花费的钱数)；现在要求任意相邻的篱笆高度不能相同，问你最少需要花费多少钱

解题思路

这是一个可以用DP来暴力的，我们枚举相邻的两个篱笆，让他们增高的方案有9种分别是 前一个不增加后一个分别增加 0 1 2，然后前一个增加 1 后一个 0 1 2；最后一种就是前一个 增加 2 后一个增加 0 1 2；这样就可以枚举每一种可能了，并且很巧妙的是一个栏杆增加这三种可能刚好可以满足要求。我们只需要用dp来记录下上一个状态然后一直继续下去就行了（这个题好像要用scanf，和printf不然有可能会TLE）

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll a[300009],b[300009];
ll dp[300009][3];

int main()
{
    ios::sync_with_stdio(false);
    int n,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i]>>b[i];
        dp[0][0]=0;dp[0][1]=b[0];dp[0][2]=b[0]*2;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<3;j++)
            {
                dp[i][j]=2e18;
                for(int k=0;k<3;k++)
                {
                    if(a[i-1]+k!=a[i]+j)
                    {
                        dp[i][j]=min(dp[i][j],dp[i-1][k]+b[i]*j);
                    }
                }
            }
        }
        cout<<min(dp[n-1][0],min(dp[n-1][1],dp[n-1][2]))<<"\n";
    }
    return 0; 
}