AcWing 5400. 蜗牛
原题链接
中等
作者:
tire
,
2025-04-10 20:38:24
· 山西
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
const int mod = 100003;
int n,m;
int qmi(int a,int k){
int res = 1;
while(k){
if(k&1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
int a[N],b[N];
int x[N];
double dp[N][3];
void solve(){
cin >> n;
for(int i = 1;i<=n;i++) cin >> x[i];
for(int i = 0;i<=n;i++){
for(int j = 0;j<=1;j++){
dp[i][j] = 2e9;
}
}
for(int i = 1;i<n;i++){
cin >> a[i] >> b[i + 1];
}
dp[1][0] = x[1];
for(int i = 2;i<=n;i++){
dp[i][0] = min({dp[i][0],dp[i - 1][0] + x[i] - x[i - 1],dp[i - 1][1] + x[i] - x[i - 1] + b[i - 1]/1.3});
dp[i][1] = min({dp[i][1],dp[i - 1][0] + b[i] / 0.7 + x[i] - x[i - 1],dp[i - 1][0] + a[i - 1] / 0.7});
if(b[i-1]>a[i - 1]){
dp[i][1] = min({dp[i][1],dp[i - 1][1]+(b[i - 1] - a[i - 1])/1.3});
}else{
dp[i][1] = min({dp[i][1],dp[i - 1][1] + (a[i - 1] - b[i - 1]) / 0.7});
}
}
printf("%.2lf",min(dp[n][0],dp[n][1]+b[n]*1.0/1.3));
}
signed main(){
int _ = 1;
while(_--){
solve();
}
return 0;
}