[bzoj2259][Oibh]新型计算机_Dijkstra
新型计算机 bzoj-2259 Oibh
题目大意：给定一个n个数的数列，第i个数为a[i]，更改第i个数至x的代价为|x-a[i]|。求最小代价，使得：读入一个数s1后，向后连着读s1个数，然后如s2，再向后读s2个数。保证最后恰好读到第n个数。
注释：$1\le n\le 10^6$
想法：又开始了... ...在那里一顿dp...
结果又是一个图论题.. ..这场面好熟悉
我们直接从第i个数像第i+a[i]连一条边权为0的边。然后这时我们思考暴力怎么做？暴力的话从i+a[i]开始像左右依次连边权为1,2,3...的边，然后Dijkstra即可，时空复杂度均为$O(n^2)$。如何优化这一过程？我们思考：其实这中的有些边是没有用的，我们只需要将相邻两个点之间连一条边权为1的边即可。然后堆优化Dij，时间复杂度为O(nlogn)。
正确性：我们发现：绝对值函数f(x)=|x|是一个偶函数，而且是一个线性偶函数，所以这东西支持在符号相同的情况下加减，在符号不同的情况下可以直接通过我们连的边退回去，证毕。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 1000010
#define mp make_pair
using namespace std;
priority_queue<pair<int,int> > pq;
int to[N<<2],nxt[N<<2],val[N<<2],head[N],tot;
int dis[N]; bool lv[N],rv[N],vis[N];
inline void add(int x,int y,int z)
{
to[++tot]=y;
val[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
int main()
{
int n; cin >> n ;
for(int u,i=1;i<=n;i++)
{
scanf("%d",&u);
if(i+u>n) add(i,n+1,i+u-n);
else add(i,i+u+1,0);
for(int j=i+1;j<=i+u+1&&j<=n&&!lv[j];j++) lv[j]=1,add(j,j-1,1);
for(int j=i+u+1;j<=n&&!rv[j];j++) rv[j]=1,add(j,j+1,1);
}
memset(dis,0x3f,sizeof(dis));
pq.push(mp(0,1)),dis[1]=0;
while(!pq.empty())
{
int u=pq.top().second; pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=nxt[i])
if(dis[to[i]]>dis[u]+val[i])
dis[to[i]]=dis[u]+val[i],pq.push(mp(-dis[to[i]],to[i]));
}
printf("%d\n",dis[n+1]);
return 0;
}
小结：图论真tm难... ...
