记录编号	48697	评测结果	AAAAAAAA
题目名称	过河	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2012-11-06 14:06:06	内存使用	5.11 MiB

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a[1002][2],b,c,d,f[1002][1001],l,m,n;
bool bo[1002][1001],boo[1002];
queue <int> q;
int main(void)
{
    freopen("rivera.in","r",stdin);
    freopen("rivera.out","w",stdout);
	scanf("%d",&b);
	for (c=1;c<=b;c++)
	{
		scanf("%d%d",&a[c][0],&a[c][1]);
		d=1;
		while (d<=1000) 
		{
			l=d+a[c][0];
			for (;d<l;d++) 
			{
				if (d>1000) break;
				bo[c][d]=true;
			}
			d+=a[c][1];
		}
	}
	for (c=0;c<=1000;c++) 
	{
		bo[b+1][c]=true;
		bo[0][c]=true;
	}
	q.push(0);
	boo[0]=true;
	for (c=1;c<=1000;c++)
	{
		n=q.size();
		if (n==0) 
		{
			printf("NO");
			return 0;
		}
		for (d=0;d<n;d++)
		{
			m=q.front();
			for (l=m-1;l>=0&&l>=m-5;l--)
				if (bo[l][c]==true)
				{
					if (boo[l]==false) 
					{
						boo[l]=true;
						q.push(l);
					}
				}
			for (l=m+1;l<=m+5&&l<=b+1;l++)
				if (bo[l][c]==true)
				{
					if (l==b+1)
					{
						printf("%d",c);
						return 0;
					}
					if (boo[l]==false) 
					{
						boo[l]=true;
						q.push(l);
					}
				}
			q.pop();
			boo[m]=false;
			if (bo[m][c]==true) 
			{
				q.push(m);
				boo[m]=true;
			}
		}
	}
	printf("NO");
	fclose(stdin);
    fclose(stdout);
    return 0;
}