Description:

Tim 正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。
但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数 —— 自然数包括0），计算机先读取第一个数字 $S1$ ，然后顺序向后读入 $S1$ 个数字。接着再读一个数字 $S2$ ，顺序向后读 入 $S2$ 个数字 …… 依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处理数据，否则计算机就会进行自毁性 操作！
Tim 现在有一串输入序列。但可能不是合法的，也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改，加上一个数或者减去一个数，当然，仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。
不过 Tim 还希望更改的总代价最小，所谓总代价，就是对序列中每一个数操作的参数的绝对值之和。
写一个程序：
从文件中读入原始的输入序列； 计算将输入序列改变为合法序列需要的最小代价；
向输出文件打印结果。

Input

输入文件包含两行，第一行一个正整数 $N$ ， $N<1e^6+1$ 。
输入文件第二行包含 $4$ 个自然数，表示输入序列。

Output

仅一个整数，表示把输入序列改变为合法序列需要的最小代价，保证最小代价小于 $1e^9$ 。

Sample Input

4
2 2 2 2

Sample Output

1

Solution:

这道题居然是个图论最短路。

以修改的代价为边权建图，显然 $$ 的边权为0。

当 $i+a_i+1>n+1$ 时 $$ 的边权为 $a_i+i-n$ 。

同时可以将 $$ 和 $$ 的边权为1。

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
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int inf=0x7fffffff;
struct edge{
	int u,v,w,nxt;
}e[maxn<<2];
int cnt,h[maxn<<1];
void add(int u,int v,int w){
	e[++cnt]=(edge){u,v,w,h[u]};
	h[u]=cnt;
}
int n,a[maxn],dis[maxn];
struct node{
	int v,w;
	friend bool operator <(const node &a,const node &b){
		return a.w>b.w;
	}
};
priority_queue<node> q;
void dijstra(int be){
	for(int i=1;i<maxn;i++) dis[i]=inf;
	dis[be]=0;
	q.push((node){be,0});
	while(!q.empty()){
		int u=q.top().v,dist=q.top().w;q.pop();
		if(dist!=dis[u]) continue;
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				q.push((node){v,dis[v]});
			}
		}
	} 
}
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int minn=inf;
	for(int i=1;i<=n;i++){
		minn=min(minn,i+a[i]+1);
		if(i+a[i]<=n) add(i,i+a[i]+1,0);
		else add(i,n+1,i+a[i]-n);
	}
	for(int i=minn;i<=n;i++) add(i,i+1,1);
	for(int i=1;i<=n;i++) add(i+1,i,1);
	dijstra(1);
	printf("%d\n",dis[n+1]);
	return 0;
}