记录编号	48752	评测结果	AAWAWAWW
题目名称	过河	最终得分	50
用户昵称	Cloud	是否通过	未通过
代码语言	C++	运行时间	0.018 s
提交时间	2012-11-06 15:17:14	内存使用	12.81 MiB

#include<fstream>
#include<queue>
using namespace std;
struct yu
{
	int p;
	int t;
};
yu tmp;
queue<yu> dq;
bool f[1000][10001];
int main(void)
{
	ifstream fin("rivera.in");
	ofstream fout("rivera.out");
	int n;
	int s[1000][2];
	int i,j,k;
	fin>>n;
	for(i=0;i<n;i++)
		fin>>s[i][0]>>s[i][1];
	for(i=0;i<5;i++)
		if(1%(s[i][0]+s[i][1])<=s[i][0]&&1%(s[i][0]+s[i][1]))
		{
			tmp.t=1;
			tmp.p=i;
			dq.push(tmp);
			f[tmp.p][tmp.p]=1;
		}
	while(dq.size())
	{
		tmp=dq.front();
		i=s[tmp.p][0]-tmp.t%(s[tmp.p][0]+s[tmp.p][1]);
		for(j=0;j<=i;j++)
			for(k=tmp.p+1;k<=tmp.p+5;k++)
			{
				tmp=dq.front();
				tmp.t+=j;
				if((tmp.t+1)%(s[k][0]+s[k][1])<=s[k][0]&&(tmp.t+1)%(s[k][0]+s[k][1]))
				{
					tmp.t++;
					tmp.p=k;
					if(tmp.p+5>=n)
					{
						fout<<tmp.t+1;
						return 0;
					}
					if(!f[tmp.p][tmp.t])
					{
						dq.push(tmp);
						f[tmp.p][tmp.t]=1;
					}
				}
			}
		dq.pop();
	}
	fout<<"NO";
	fin.close();
	fout.close();
	return 0;
}