KY23 最小花费 DP
2024-01-08 11:53:35
DP,比较恼的是题中没说明a、b的范围,不敢轻易用双循环
添加链接描述
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9 + 10;
int l1, l2, l3, c1, c2, c3, a, b, n;
int pri(int d){
if(d <= l1) return c1;
else if(d <= l2) return c2;
return c3;
}
int main()
{
while(cin>>l1>>l2>>l3>>c1>>c2>>c3>>a>>b>>n){
vector<ll>p(n + 1, 0);
vector<ll>dp(n + 1, INF); //dp[i]表示从第一个站到第i个站的最短距离
for(int i = 2; i <= n; i ++ ){
cin>>p[i]; //p[i]表示第1个站到第i个站的距离
}
p[1] = 0;
dp[a] = 0;
for(int i = a + 1; i <= b; i ++ ){ //这一次下车的站
for(int j = a; j < i; j ++ ){ //上一次下车的站
int d = p[i] - p[j]; //两个车站间的距离
if(p[i] - p[j] <= l3){
dp[i] = min(dp[i], dp[j] + pri(d));
}
}
}
cout<<dp[b]<<endl;
}
return 0;
}
文章来源:https://blog.csdn.net/qiaodxs/article/details/135452548
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!