题目链接：
1.蜗牛 - 蓝桥云课 (lanqiao.cn)
思路说明：
首先，考虑DFS暴力解：对于蜗牛来说，它出发的起点可能是：
1、Xi竹竿底部2、从上一根杆Xi-1传送门传送到的bi，
那么他有三种方式走，
从Xi竹竿底部沿着x轴爬过去到Xi+1从bi向上或者向下爬到ai，通过传送门到达下一根竿，也就是（xi+1，bi+1） 从bi直接滑到当前竹竿底部
这就形成了dfs三个递归搜索的分支，终止条件是到达目标点，剪枝函数是所用时间大于已经找到的最小时间（初始值设置为原点到目标点的x差值）时，返回。
需要参数保存当前的x，y坐标，当前已经花了的时间，因为竹竿和传送门保存在数组里，我们需要传递索引来确定走到哪一根竹竿了。
注意：结果要保留两位小数，可以使用c语言的格式控制。
每个dfs的条件（见程序），最后一根竿是没有传送门的，所以最后一根杆不能走传送门 的dfs，要进行判断。
还有从第一根竿开始，最后结果还要加上原点到第一根竿的时间。
DFS代码如下：
#include
#define int long long
#define endl '\n'
using namespace std;
int ans = 0;
vector
vector
int n=0;
double mint=0;
void dfs(int cx,int cy,double t,int i){
if(t>mint) return;
if(cx==x[n]&&cy==0){
if(t mint=t; } return; } /* 错误代码：在选择爬到该杆子的a[i]使用魔法时，没有考虑到用魔法跳到下一根杆子的时候，不是从0往上爬，而是根据跳到的bi+1（cy）与ai+1的相对位置 决定向上 还是 向下爬 ，爬的距离是cy和ai+1的相对距离 if(cy==0) dfs(x[i+1],b[i+1],t+a[i]/0.7,i+1); if(cy==0) dfs(x[i+1],0,t+(x[i+1]-x[i]),i+1); if(cy>0) dfs(x[i],0,t+cy/1.3,i);*/ //注意 if(cy>=a[i]&&cx!=x[n]) dfs(x[i+1],b[i+1],t+(cy-a[i])/1.3,i+1); if(cy if(cy>0) dfs(x[i],0,t+cy/1.3,i); if(cy==0&&cx!=x[n]) dfs(x[i+1],0,t+(x[i+1]-x[i]),i+1); } signed main() { cin.tie(0); cout.tie(0); cin>>n; x.push_back(0);a.push_back(0);b.push_back(0);b.push_back(0); for(int i=1;i<=n;i++){ int xi; cin>>xi; x.push_back(xi); } for(int i=1;i<=n-1;i++){ int ai,bj; cin>>ai>>bj; a.push_back(ai); b.push_back(bj); } mint=x[n]-x[1]; dfs(x[1],0,0,1); printf("%.2f",mint+x[1]); return 0; } 在比赛中，首先要保证暴力做出来拿到一些分数，再考虑优化。由于n的数据范围到达了， 所以肯定是会超时的，时间复杂度O()。于是考虑动态规划。 //怎么比较自然地想到动态规划的解决方式： //考虑达到终点即xn竹竿的底部（xn，0）的方式，可以从 （Xn-1，0）沿着x轴爬过去，或者从（Xn-1 ，a[n-1]） //通过传送门到达(Xn ，b[n]) ， 再从这个地方顺着竹竿下滑到达 （xn，0） //如果只使用一个dp数组保存到达xi竹竿底部的最短时间，我们无法计算出到达xi+1底部的最短时间 //因为无法确认求出来的当前最短时间是否是从传送门终点滑下来的还是从上一个竹竿沿着x轴爬过来的 //所以还需要一个dp数组来保存到达每根竹竿的传送门起点的最短时间 //这提示我们，线性的动态规划可能需要不止一个dp数组来递推，根据需要来设计 关于递推公式，网上题解已经足够丰富，不再赘述。 代码如下： //#include //#include #include #define int long long #define endl '\n' using namespace std; const int N = 1e5+10; int ans = 0; vector vector int n=0; //double mint=0; double bottom[N],tran[N]; //怎么比较自然地想到动态规划的解决方式： //考虑达到终点即xn竹竿的底部（xn，0）的方式，可以从 （Xn-1，0）沿着x轴爬过去，或者从（Xn-1 ，a[n-1]） //通过传送门到达(Xn ，b[n]) ， 再从这个地方顺着竹竿下滑到达 （xn，0） //如果只使用一个dp数组保存到达xi竹竿底部的最短时间，我们无法计算出到达xi+1底部的最短时间 //因为无法确认求出来的当前最短时间是否是从传送门终点滑下来的还是从上一个竹竿沿着x轴爬过来的 //所以还需要一个dp数组来保存到达每根竹竿的传送门起点的最短时间 //这提示我们，线性的动态规划可能需要不止一个dp数组来递推，根据需要来设计 signed main() { cin.tie(0); cout.tie(0); cin>>n; x.push_back(0);a.push_back(0);b.push_back(0);b.push_back(0); for(int i=1;i<=n;i++){ int xi; cin>>xi; x.push_back(xi); } for(int i=1;i<=n-1;i++){ int ai,bj; cin>>ai>>bj; a.push_back(ai); b.push_back(bj); } bottom[1]=x[1],tran[1]=x[1]+a[1]/0.7; for(int i=2;i<=n;i++){ bottom[i]=min(bottom[i-1]+x[i]-x[i-1],tran[i-1]+b[i]/1.3); double dis=0; if(b[i]>=a[i]) dis=(b[i]-a[i])/1.3; else dis=(a[i]-b[i])/0.7; tran[i]=min(bottom[i-1]+x[i]-x[i-1]+a[i]/0.7,tran[i-1]+dis); } //保留两位小数 printf("%.2f",bottom[n]); return 0; } 相关链接
发表评论