DP 简单题
时间复杂度
$O(n)$
C++ 代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int n, x[maxn], a[maxn], b[maxn];
double f[maxn][2];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> x[i];
for (int i = 1; i < n; i++) cin >> a[i] >> b[i + 1];
// 初始化
f[1][0] = x[1], f[1][1] = x[1] + (double)a[1] / 0.7;
for (int i = 2; i <= n; i++)
{
// 从前一根柱子底端爬过去 或 传送并下滑
f[i][0] = min(f[i - 1][0] + x[i] - x[i - 1], f[i - 1][1] + (double)b[i] / 1.3);
// 从当前柱子底端爬上 或 传送并上下爬
double dist = a[i] - b[i]; // a, b 间高度差
f[i][1] = min(f[i][0] + (double)a[i] / 0.7, f[i - 1][1] + (dist > 0 ? dist / 0.7 : -dist / 1.3));
}
cout << fixed << setprecision(2) << f[n][0] << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}