18718 航行(深搜/暴力）

蔚落 2023-07-25 12:49 24阅读 0赞

## 题目 ##

Description  
银河帝国正走向覆亡。为保留文明的种子，你需要驾驶飞船将一批“颛家”从帝国首都护送至银河边缘的基地。  
现在已知航线是一条直线，帝国首都为起点（坐标0），基地为终点（坐标L），在这条航线上有N个空间站可以补充飞船的能源。  
第i个空间站的坐标为ai，飞船停靠在第i个空间站必须花费bi个银河币，同时让你的飞船能量恢复为最大值M。  
出发前飞船的能量是满额的M，每一点能量都可以让飞船航行一个坐标单位。

现在你已经通过募捐(榨篇）获得了S个银河币，请计算下飞船能否到达基地。

## 输入格式 ##

第一行输入四个个数字N,L,M,S；(1<=N<=200) (1<=L<=20000) (1<=M<=20000) (0<=S<=20000)  
接下来N行，每行输入两个数字，ai，bi (0<=ai<=L) (0<=bi<=20000)

## 输出格式 ##

仅一行，如果能到达基地，输出Yes，否则输出No

## 输入样例 ##

1 10000 5000 20000  
5000 20000

## 输出样例 ##

Yes

提示  
样例说明，飞船可以花费5000能量到达一号空间站，花光20000银河币补满能量后，再行驶5000到达基地。  
程序设计和数据结构设计都要考虑边缘数据。例如本题目，可能存在无需补给就直接行驶到基地的情况，也能存在bi>s的情况。

\*\*解题思路：\*\*直接深搜，每走一步就判断能否走下一步，还要比较余额等

#include<iostream>
    using namespace std;
    struct node 
    { 
    	int a,b;//坐标，花费 
    }space[250];
    int OK;
    int N,L,M,S;
    void  dfs(int money,int energy,int pos,int space_num)
    { 
    	if(pos+energy>=L)
    	{ 
    		OK=1;
    		return ;
    	}
    	for(int i=space_num+1;i<=N;i++)
    	{ 
    		if(money>=space[i].b&&energy>=space[i].a-pos)
    		{ 
    			dfs(money-space[i].b,M,space[i].a,i);
    		}
    	}
    }
    int main()
    { 
    	cin>>N>>L>>M>>S;
    	for(int i=1;i<=N;i++)
    	cin>>space[i].a>>space[i].b;
    	if(M>=L)
    	OK=1;
    	else
    	dfs(S,M,0,0);
    	if(OK)
    	cout<<"Yes"<<endl;
    	else
    	cout<<"No"<<endl;
    	return 0;
    }