比赛 20121106 评测结果 AAAAAAAA
题目名称 过河 最终得分 100
用户昵称 QhelDIV 运行时间 0.049 s
代码语言 C++ 内存使用 7.11 MiB
提交时间 2012-11-06 10:43:40
显示代码纯文本
#include <fstream>
using namespace std;
ifstream fin("rivera.in");
ofstream fout("rivera.out");
bool f[2001][2001];
const int R[12]={0,-5,-4,-3,-2,-1,0,1,2,3,4,5};
int A[2001],B[2001],N;
void Initialize()
{
int i;
	fin>>N;
	for(i=1;i<=N;i++)
		fin>>A[i]>>B[i];
}
void Dp()
{
int Ti,j,k;
	f[0][0]=true;A[0]=1000000;A[N+1]=1000000;
	for(Ti=1;Ti<=1000;Ti++)
	{
		for(j=0;j<=N+1;j++)
			if(Ti%(A[j]+B[j])<=A[j] && Ti%(A[j]+B[j])!=0)
			for(k=1;k<=11;k++)
				if(j+R[k]>=0 && j+R[k]<=N+1)
					f[Ti][j]=f[Ti][j]||f[Ti-1][j+R[k]];
		if(f[Ti][N+1]==true)
		{
			fout<<Ti<<endl;
			break;
		}
	}
	if(Ti==1001 && f[Ti][N+1]==false)
		fout<<"NO"<<endl;
}
int main()
{
	Initialize();
	
	Dp();
	
	fin.close();
	fout.close();
	return 0;
}