题目描述

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

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

核焰，可融真金。

咳咳。

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

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

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

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

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

数据范围

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

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

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

解法

动态规划；

设f[i]为在i与i+1之间切分最小代价和，那么f[n]就是答案。

利用队列维护一个类似阶梯状，对于同一梯度，由于f递增，所以只需维护同一梯度最前的值。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

using namespace std;

const char* fin="array.in";

const char* fout="array.out";

const int maxn=100007,maxt=maxn*4;

int n,i,j,k,v,LAST,inf;

int f[maxn],a[maxn][2];

int la[maxn],last[maxn];

int c[maxt];

void change(int l,int r,int t,int v,int v1){

    int mid=(l+r)/2;

    if (l==r){

        c[t]=v1;

        return;

    }

    if (v<=mid) change(l,mid,t*2,v,v1);

    else change(mid+1,r,t*2+1,v,v1);

    c[t]=min(c[t*2],c[t*2+1]);

}

int getmin(int l,int r,int t,int v1,int v2){

    int mid=(l+r)/2;

    if (l>v2 || r<v1) return inf;

    if (l>=v1 && r<=v2) return c[t];

    return min(getmin(l,mid,t*2,v1,v2),getmin(mid+1,r,t*2+1,v1,v2));

}

struct qual{

    int data[maxn],id[maxn],head,tail;

    qual(){

        head=1;

        tail=0;

    }

    void push(int v){

        if (tail-head<0 || data[tail]!=0){

            data[++tail]=0;

            id[tail]=v;

            change(1,n,1,tail,f[v]);

        }

    }

    void pull(int v){

        while (tail-head>=0 && data[tail]<v) tail--;

        if (tail-head<0 || data[tail]>v){

            tail++;

            data[tail]=v;

            change(1,n,1,tail,f[id[tail]]+data[tail]);

        }

    }

    void update(int v,int v1){

        while (tail-head>=1 && id[head+1]<v) head++;

        if (tail-head>=0 && id[head]<v){

            id[head]=v;

            change(1,n,1,head,f[id[head]]+data[head]);

        }

    }

    int top(){

        return tail-head>=0?getmin(1,n,1,head,tail):inf;

    }

}q;

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d",&n);

    for (i=1;i<=n;i++){

        scanf("%d%d",&a[i][0],&a[i][1]);

        last[i]=la[a[i][0]];

        la[a[i][0]]=i;

    }

    memset(f,127,sizeof(f));

    memset(c,127,sizeof(c));

    inf=c[0];

    f[0]=0;

    q.push(0);

    for (i=1;i<=n;i++){

        k=0;

        LAST=max(LAST,last[i]);

        q.update(LAST,i);

        q.pull(a[i][1]);

        f[i]=q.top();

        q.push(i);

    }

    printf("%d",f[n]);

    return 0;

}

启发

这道题演绎比较显然，很快会想出动态规划。

考虑答案的贡献，结合交集优化。

同一梯度的大多状态都是冗余的。