CODE FESTIVAL 2014 あさプロHard : B - ぽよぽよ

割と典型かな。
http://code-festival-2014-morning-hard.contest.atcoder.jp/tasks/code_festival_morning_med_d

問題

N匹の生物がいる。
各生物は単調増加列であるP[i]の位置にある杭から、距離L[i]以内の整数座標のどこかにいる。
すなわち、i番目の生物の座標X[i]について、P[i]-L[i]≦X[i]≦P[i]+L[i]である。
また、i＜jならX[i]＜X[j]である。

上記条件を満たすX[i]の組み合わせは何通りか。

解法

各X[i]について、X[j]≦X[i]-1となるX[j]の組み合わせの総和を取ればよい。
これは累積和を使うDPで容易に解くことができる。

P[i]の値は大きいが、各生物はP[i]-L[i]≦X[i]≦P[i]+L[i]の範囲だけDPを行うことでO(max(L)*N)の計算量ですむ。

int N;
ll P[1002],L[1002];
ll dp[1002][2006],S[1002][2006];
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	P[0]=-1LL<<40;
	FOR(i,N) cin>>P[i+1]>>L[i+1];
	x=0;
	
	dp[0][1003]=1;
	for(i=1003;i<=2005;i++) S[0][i]=1;
	for(i=1;i<=N;i++) {
		for(x=-L[i];x<=L[i];x++) {
			ll p=x+(P[i]-P[i-1]);
			dp[i][1003+x]=S[i-1][min(2005LL,1003+p-1)];
			S[i][1003+x]=(((1003+x>0)?S[i][1003+x-1]:0)+dp[i][1003+x])%mo;
		}
		for(x=L[i]+1;x<=1003;x++) S[i][1003+x]=S[i][1003+x-1];
	}
	cout << S[N][2005] << endl;
}

まとめ

累積和を使うDPの典型例だね。