比赛 |
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;
}