解题思路:
//先分别求到1,2,3,。。。15站的min
//第15站的min是踩在前面站的min上来的
//i=2,k=1;minv=min(minv,dp[1]+pri[1])=min(50000,12+12)=24
//因为i>=k,所以还可以继续内循环,->i=2,k=2;
//minv=min(minv,dp[0]+pri[2])=min(24,21)=21
//以上过程就是比较所有可以到第2站的方法中的min,最后将其永久记录,求第3站用
注意事项:
参考代码:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int pri[100]={0}; //每公里所需要的价钱
int dp[100]={0}; //每个状态(公里)最小开销
int n; //所要行驶总公里数
for(int i=1;i<=10;i++)
{
cin>>pri[i];
}
cin>>n;
dp[1]=pri[1];//第一公里毋庸置疑,只有一种乘车方案
for(int i=2;i<=n;i++)
{
int minv=50000;
//所有方案是:之前的某个位置(i-k)坐k(k=1,2,3...10)公里到当前位置
//当然,上面说的i-k可能小于0,所以注意
for(int k=1;k<=10&&i-k>=0;k++)
{
minv=min(minv,dp[i-k]+pri[k]);
}
//找到最小开销并存储到当前dp节点
dp[i]=minv;
}
cout<<dp[n];//最后一个dp节点保存的即所有公里的最小开销
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:633 |
C语言考试练习题_排列 (C语言代码)浏览:725 |
WU-蓝桥杯算法提高VIP-勾股数 (C++代码)浏览:1607 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:683 |
大神老白 (C语言代码)浏览:601 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:771 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:657 |
C语言程序设计教程(第三版)课后习题7.3 (C++代码)浏览:462 |
简单的a+b (C语言代码)浏览:558 |
纪念品分组 (C++代码)浏览:838 |