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