D. 停不下来的团长奥尔加 动态规划

• 2020 年 10 月 29 日
• 筆記
• 动态规划, 数据结构

题目描述

分析

设\(f[i]\) 为从 \(i\) 走到 \(i+1\) 的步数
初始值 \(f[i]=2\)
则 \(f[i]=\sum_{i=p[i]}^{i}f[i]\)
考试的时候用树状数组维护的前缀和
其实这东西也可以拿一个数组记录

代码

#include<cstdio>
#include<cstring>
#define rg register
const int maxn=1e6+5;
const int mod=1e9+7;
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
int tr[maxn],n,a[maxn],f[maxn];
int lb(int xx){
	return xx&-xx;
}
int cx(int wz){
	int nans=0;
	for(rg int i=wz;i>0;i-=lb(i)){
		nans+=tr[i];
		if(nans>=mod) nans-=mod;
	}
	return nans;
}
void ad(int wz,int val){
	for(rg int i=wz;i<maxn;i+=lb(i)){
		tr[i]+=val;
		if(tr[i]>=mod) tr[i]-=mod;
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	rg int nans;
	for(int i=1;i<=n;i++){
		nans=cx(i)-cx(a[i]-1)+2;
		nans=(nans+mod)%mod;
		ad(i,nans);
	}
	printf("%d\n",cx(n));
	return 0;
}