比赛 |
NOIP2008集训模拟5 |
评测结果 |
AWTTTTTTTA |
题目名称 |
越狱 |
最终得分 |
20 |
用户昵称 |
BYVoid |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-14 09:22:43 |
显示代码纯文本
#include <iostream>
using namespace std;
const int MAXN=10001;
const int MAXM=3001;
const int INF=0x7FFFFFFF;
struct Station
{
int d,o;
};
int N,L,P,Ans=INF;
Station S[MAXN];
int F[MAXN][MAXM];
int Max[MAXN],Min[MAXN];
inline int cmp(const void *a,const void *b)
{
return ((Station * )a)->d - ((Station * )b)->d;
}
void init()
{
int i;
freopen("prisonbreak.in","r",stdin);
freopen("prisonbreak.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d%d",&S[i].d,&S[i].o);
}
scanf("%d%d",&L,&P);
for (i=1;i<=N;i++)
{
S[i].d=L-S[i].d;
Min[i]=INF;
}
S[++N].d=L;
S[0].o=P;
qsort(S+1,N,sizeof(S[0]),cmp);
F[0][P]=1;
Min[0]=Max[0]=P;
for (i=0;i<MAXM;i++)
F[N][i]=INF;
}
void dynamic()
{
int i,j,k,l;
for (i=0;i<N;i++)
{
for (j=Min[i];j<=Max[i];j++)
{
if (!F[i][j]) continue;
for (k=i+1;k<=N && (l=j-(S[k].d-S[i].d))>=0;k++)
{
F[k][l+S[k].o]=F[i][j]+1;
if (l+S[k].o>Max[k])
Max[k]=l+S[k].o;
if (l+S[k].o<Min[k])
Min[k]=l+S[k].o;
}
}
}
for (i=Min[N];i<=Max[N];i++)
{
if (F[N][i]<Ans)
Ans=F[N][i];
}
if (Ans==INF) Ans=1;
Ans-=2;
}
int main()
{
init();
dynamic();
cout << Ans;
return 0;
}