KY23 最小花费 DP

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

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！