input:array.in output:array.out

Time Limits: 1000 ms Memory Limits: 131072 KB

Description

在炽热的核熔炉中，居住着一位少女，名为灵乌路空。
据说，从来没有人敢踏入过那个熔炉，因为人们畏缩于空所持有的力量——核能。
核焰，可融真金。

咳咳。
每次核融的时候，空都会选取一些原子，排成一列。然后，她会将原子序列分成一些段，并将每段进行一次核融。
一个原子有两个属性：质子数和中子数。
每一段需要满足以下条件：
1、同种元素会发生相互排斥，因此，同一段中不能存在两个质子数相同的原子。
2、核融时，空需要对一段原子加以防护，防护罩的数值等于这段中最大的中子数。换句话说，如果这段原子的中子数最大为x，那么空需要付出x的代价建立防护罩。求核融整个原子序列的最小代价和。

Input

第一行一个正整数N，表示原子的个数。
接下来N行，每行两个正整数pi和ni，表示第i个原子的质子数和中子数。

Output

输出一行一个整数，表示最小代价和。

Sample Input

1
2
3
4
5
6
5
3 11
2 13
1 12
2 9
3 13

Sample Output

1
26

Data Constraint

对于20%的数据，1<=n<=100
对于40%的数据，1<=n<=1000
对于100%的数据，1<=n<=10^5，1<=pi<=n，1<=ni<=2*10^4

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<set> 
using namespace std;
multiset<int>t;
int tmp,n,m,ans=0,start,end;
int data[100005],a[100005],b[100005],hou[100005],l[100005];
int sum[100005],wei[100005],f[100005];
int main()
{
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
    	 scanf("%d%d",&a[i],&b[i]);
	}
    for (int i=1;i<=n;i++){
    	 l[i]=hou[a[i]]+1,hou[a[i]]=i;
	}
    for (int i=1;i<=n;i++){
    	 l[i]=max(l[i-1],l[i]);
	}
    start=1;
    for (int i=1;i<=n;i++) 
	{
        tmp=i-1;
        while(start<end&&wei[start+1]<l[i])
		{
            t.erase(t.find(sum[start]));
            start++;
        }
        while(start<=end&&b[i]>data[end])
		{
            t.erase(t.find(sum[end]));
            tmp=wei[end];
            end--;
        }
        data[++end]=b[i];
        wei[end]=tmp;
        if(start!=end)
		{
            sum[end]=f[wei[end]]+data[end];
            t.insert(sum[end]);
            t.erase(t.find(sum[start]));
        }
        sum[start]=f[l[i]-1]+data[start];
        t.insert(sum[start]);
        f[i]=*t.begin();
    }
    printf("%d\n",f[n]);
}