题目分析
题目的大概意思是需要求到x轴上的最后一个点的最短时间,根据这个最终目标我们可以确定我们的状态集合,因为到x轴上的最后一个点有三条路径可以走,分别是x[i-1]这个点沿x轴爬行到x[i],以及x[i-1]这条竹竿上的传送点向下到x[i-1]再沿x轴到x[i],第三条路径是通过x[i-1]这根竹竿上的传送门传送到x[i]这根竹竿上在向下爬到x[i],因为需要确定到x[i-1]这条竹竿上的传送门的最短时间,所以就增加一个状态表示到每根竹竿上的传送门的最短时间;
关键代码
dp[i][0]=min(dp[i-1][0]+x[i]-x[i-1],dp[i-1][1]+b[i-1]/1.3);
dp[i][0]=min(dp[i][0],dp[i-1][1]+a[i-1]/1.3+x[i]-x[i-1]);
dp[i][1]=min(dp[i-1][1]+abs(b[i-1]-a[i])/(b[i-1]>a[i]?1.3:0.7),dp[i-1][0]+a[i]/0.7+x[i]-x[i-1]);//这里算的是到a[i]
dp[i][1]=min(dp[i][1],dp[i][0]+a[i]/0.7);
dp[i][0]表示的是到x[i]所需要的最短时间
dp[i][1]表示的是到x[i]上的传送门的最短时间
C++ 代码
最后代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
double x[N],a[N],b[N];
int n;
double dp[N][2];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i];
for(int i=1;i<=n-1;i++)
cin>>a[i]>>b[i];
memset(dp, 0x7f, sizeof dp);
dp[1][0]=x[1],dp[1][1]=x[1]+a[1]/0.7;
for(int i=2;i<=n;i++)
{
dp[i][0]=min(dp[i-1][0]+x[i]-x[i-1],dp[i-1][1]+b[i-1]/1.3);
dp[i][0]=min(dp[i][0],dp[i-1][1]+a[i-1]/1.3+x[i]-x[i-1]);
dp[i][1]=min(dp[i-1][1]+abs(b[i-1]-a[i])/(b[i-1]>a[i]?1.3:0.7),dp[i-1][0]+a[i]/0.7+x[i]-x[i-1]);//这里算的是到a[i]
dp[i][1]=min(dp[i][1],dp[i][0]+a[i]/0.7);
}
printf("%.2lf\n",dp[n][0]);
return 0;
}