# 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.

## 代码

```#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;
} ```

0 条评论

• ### D. Shortest and Longest LIS

time limit per test3 seconds memory limit per test256 megabytes inputstandard in...

• ### C. NEKO's Maze Game

time limit per test:1.5 seconds memory limit per test:256 megabytes inputstandar...

• ### 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

• ### 【人工智能】45测试深度学习基础知识的数据科学家的问题（以及解决方案）

早在2009年，深度学习只是一个新兴领域。只有少数人认为它是一个富有成果的研究领域。今天，它被用于开发一些被认为是难以做到的事情的应用程序。

• ### RL08 Uncertainty & Bayesian Networks

Learningunder uncertainly is where an agent decides what to do when it does not ...

• ### 45测试深度学习基础知识的数据科学家的问题（以及解决方案）

原文:https://www.analyticsvidhya.com/blog/2017/01/must-know-questions-deep-learnin...

• ### HDUOJ---2955 Robberies

Robberies Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

• ### POJ 2209 The King(简单贪心)

The King Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7499...

• ### jQuery的attr方法处理checkbox的问题

使用了 jQuery 1.10 的版本，想实现 checkbox 的全部选中和全部取消选中，使用了 attr 的方法，如下：

• ### POJ-1458 Common Subsequence（线性动规，最长公共子序列问题）

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submis...