【HDU】4405 Aeropline checs

http://acm.hdu.edu.cn/showproblem.php?pid=4405
毎回1~6格を歩いて0段目に初期化し、>=nまで歩くと格子が終わります.また、m個の転送ゲートは、消費回数を必要とせずにX[i]ビンからY[i]に転送できることを示しています.n<=100000,m<=1000.

#include <cstdio>

#include <cstring>

using namespace std;

double d[100010];

int n, m, mp[100010], X[1005], Y[1005];

int main() {

	while(scanf("%d%d", &n, &m), !(n==0&&m==0)) {

		for(int i=0; i<m; ++i) scanf("%d%d", &X[i], &Y[i]);

		for(int i=0; i<m; ++i) mp[X[i]]=Y[i];

		for(int i=n-1; i>=0; --i) {

			if(mp[i]) d[i]=d[mp[i]];

			else {

				d[i]=(d[i+1]+d[i+2]+d[i+3]+d[i+4]+d[i+5]+d[i+6])/6+1;

			}

		}

		printf("%.4f
", d[0]);

		memset(d, 0, sizeof(double)*(n));

		for(int i=0; i<m; ++i) mp[X[i]]=0;

	}

	return 0;

}

　　
良い裸の期待dp…移転はすべて相互に反発するので、直接やります.
複数のY[i]が重なっていると判断しにくいので、逆押しします.