灵知的太阳信仰

【题目大意】

在炽热的核熔炉中，居住着一位少女，名为灵乌路空。

据说，从来没有人敢踏入过那个熔炉，因为人们畏缩于空所持有的力量——核能。

核焰，可融真金。

 

咳咳。

每次核融的时候，空都会选取一些原子，排成一列。然后，她会将原子序列分成一些段，并将每段进行一次核融。

一个原子有两个属性：质子数和中子数。

每一段需要满足以下条件：

1.同种元素会发生相互排斥，因此，同一段中不能存在两个质子数相同的原子。

2.核融时，空需要对一段原子加以防护，防护罩的数值等于这段中最大的中子数。换句话说，如果这段原子的中子数最大为x，那么空需要付出x的代价建立防护罩。

求核融整个原子序列的最小代价和。

【数据输入】

第一行一个正整数N，表示原子的个数。

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

【数据输出】

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

【样例输入】

5

3 11

2 13

1 12

2 9

3 13

【样例输出】

26

【数据范围】

对于20%的数据，1<=n<=100

对于40%的数据，1<=n<=1000

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

---

思路：

乍一看贪心，再一看区间DP，但其实想多了

因为不能有重复的原子（质子数相同），并且区间要连续，所以我们记录每个原子可以合并的最左端

然后一个线性的更新，就好啦

这应该是40分做法，但确实能A……

正解是线段树（我也不会……）

code

#include<stdio.h> 
#include<algorithm> 
using namespace std;
const int mxn=1e5+10;
int n,id[mxn],val[mxn],to[mxn],f[mxn],l[mxn]={1};

void file() {
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout);
}
int main() 
{
//    file();
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&id[i],&val[i]);
        l[i]=l[i-1];
        if(to[id[i]]) l[i]=max(l[i],to[id[i]]+1);
         to[id[i]]=i;
    }
    for(int i=1;i<=n;++i) {
        int mx=val[i];
        f[i]=f[i-1]+val[i];
        for(int j=i-1;j>=l[i];--j) {
            mx=max(mx,val[j]);
            f[i]=min(f[i],f[j-1]+mx);
        }
    }
     printf("%d",f[n]);
    return 0;
}