题目链接:http://codeforces.com/problemset/problem/1221/D
题目大意:
q个询问。每次询问给你n个高度为a[i]的栅栏。升高第i个栅栏高度1将花费b[i]。现在要让所有的栅栏高度和相邻栅栏的高度都不同。问最小的费用是多少。

思路:由题意可以知道:每个栅栏最多升高两次。那么用dp[i][j]表示第i个栅栏升高j米满足条件的最小费用。

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

int a[300005], b[300005];
LL dp[300005][3];
int main()
{
    int q;
    scanf("%d", &q);
    while(q--){
        int n;
        scanf("%d", &n);
        for(int i=1; i<=n; i++){
            scanf("%d%d", &a[i], &b[i]);
            dp[i][0]=dp[i][1]=dp[i][2]=(1ll<<60);
        }
        dp[1][0]=0, dp[1][1]=b[1], dp[1][2]=2*b[1];
        for(int i=2; i<=n; i++){
            for(int j=0; j<3; j++){
                for(int k=0; k<3; k++){
                    if(a[i-1]+j!=a[i]+k){
                        dp[i][k]=min(dp[i][k], dp[i-1][j]+k*b[i]);
                    }
                }
            }
        }
        LL ans=(1ll<<60);
        for(int i=0; i<3; i++){
            ans=min(ans, dp[n][i]);
        }
        printf("%lld\n", ans);
    }

	return 0;
}