题目描述
在炽热的核熔炉中，居住着一位少女，名为灵乌路空。
据说，从来没有人敢踏入过那个熔炉，因为人们畏缩于空所持有的力量——核能。
核焰，可融真金。
咳咳。
每次核融的时候，空都会选取一些原子，排成一列。然后，她会将原子序列分成一些段，并将每段进行一次核融。
一个原子有两个属性：质子数和中子数。
每一段需要满足以下条件：
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;
}启发
这道题演绎比较显然，很快会想出动态规划。
考虑答案的贡献，结合交集优化。
同一梯度的大多状态都是冗余的。