4883.灵知的太阳信仰

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]);
}
暗影 微信

微信