题目 1282: 公交汽车(培养这类题的感觉)

解题思路:

//先分别求到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;

}