Make The Fence Great Again CodeForces - 1221D（动态规划）-白红宇

Make The Fence Great Again CodeForces - 1221D（动态规划）

阅读量：4135 次

发布时间：2019-05-25

本文共 2717 字，大约阅读时间需要 9 分钟。

You have a fence consisting of nn vertical boards. The width of each board is 11. The height of the ii-th board is aiai. 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 22 to nn, the condition ai−1≠aiai−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 ii-th board by 11, but you have to pay bibi 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 qq independent queries.

Input

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

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

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

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

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

Output

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

Example

Input

2 4

2 1

3 5

2 3

2 10

2 6

1 7

3 3

2 6

1000000000 2

Output

Note

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

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

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

思路：对于每个栅栏，我们要知道最多可以增加两次，增加两次之后肯定就可以保证和旁边的两个栅栏不一样高。那么我们可以枚举每个栅栏增加几次（0，1，2），但是和前一个栅栏不能一样高。

状态转移方程：dp[i][j]=min(dp[i][j],dp[i-1][k]+j*p[i].cost);//dp[[i][j]代表着第i个栅栏增加j次所花费的最小值。

代码如下：

#include
   
    #define ll long long#define inf 0x7f7f7f7fusing namespace std;const int maxx=3e5+100;struct node{
   	ll h;	ll cost;}p[maxx];ll dp[maxx][3];int n;int main(){
   	int t;	scanf("%d",&t);	while(t--)	{
   		scanf("%d",&n);		for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].h,&p[i].cost),dp[i][0]=dp[i][1]=dp[i][2]=1e18;		dp[0][0]=dp[0][1]=dp[0][2]=0;		for(int i=1;i<=n;i++)		{
   			for(int j=0;j<3;j++)			{
   				for(int k=0;k<3;k++)				{
   					if(p[i].h+j!=p[i-1].h+k)//两个栅栏不能一样。					{
   						dp[i][j]=min(dp[i][j],dp[i-1][k]+j*p[i].cost);					}				}			}		}		ll ans=1e18;		for(int i=0;i<3;i++) ans=min(ans,dp[n][i]);		cout<
    
     <

努力加油a啊，(^o)/~

转载地址：http://zftvi.baihongyu.com/

你可能感兴趣的文章