比赛 |
NOIP2008集训模拟5 |
评测结果 |
ATTTTTTTTW |
题目名称 |
越狱 |
最终得分 |
10 |
用户昵称 |
zqzas |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-14 11:23:02 |
显示代码纯文本
#include <iostream>
#define MAXN 10010
#define INF 999999
using namespace std;
typedef struct{
int dis;
int oil;
}Pos;
int n,ans;
Pos pos[MAXN];
int cmp(const void *a,const void *b)
{
return ((Pos *)a)->dis - ((Pos *)b)->dis;
}
void dfs(int x,int less,int now)
{
if (x==0)
{
if (now<ans)
ans=now;
return;
}
if (now>ans)
return;
//stop at POS x
if ( (less+pos[x].oil-(pos[x].dis-pos[x-1].dis)) >=0)
dfs(x-1,less+pos[x].oil-(pos[x].dis-pos[x-1].dis),now+1);
//no stop
if (less-(pos[x].dis-pos[x-1].dis)>=0)
dfs(x-1,less-(pos[x].dis-pos[x-1].dis),now);
}
void run()
{
ans=INF;
dfs(n,0,-1);
}
void ini()
{
int i;
cin>>n;
n++;
for (i=1;i<=n;i++)
{
scanf("%d%d",&pos[i].dis,&pos[i].oil);
}
qsort(pos,n+1,sizeof(pos[0]),cmp);
}
int main()
{
freopen("prisonbreak.in","r",stdin);
freopen("prisonbreak.out","w",stdout);
ini();
run();
printf("%d",ans);
return 0;
}