题目1282 公交汽车 [经典动态规划]

题目 1282: 公交汽车

题目描述

一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1< =n< =100），它可以通过无限次的换车来完成旅程。最后要求费用最少。

输入

第一行十个整数分别表示行走1到10公里的费用（< =500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。第二行一个整数n表示，旅客的总路程数。

输出

仅一个整数表示最少费用。

样例输入

12 21 31 40 49 58 69 79 90 101
15

样例输出

#include<bits/stdc++.h>
using namespace std;
#define max INT_MAX;
int dp[10];
int minn(int a,int b)
{
    if(a<=b) return a;
    else return b;
}
int main(void)
{
    int va[10];   //费用数组
    for(int i=0;i<10;i++) cin>>va[i];
    int num;
    cin>>num;
    dp[0]=va[0];  //初始值：走一公里最少费用没有其他可能
    for(int i=1;i<num;i++)
    {
        dp[i]=max;
        for(int j=1,n=i;j<=10&&n>=0;j++,n--)//对于每个路程的最少费用
        {         //即为该路程之前的十个公里数的费用加上到该路程的费用的最小值
            dp[i]=minn(dp[i-j]+va[j-1],dp[i]);
        }
    }
    cout<<dp[num-1];
    return 0;
}

经典动态规划，不过也是刚理解动态规划，没写过这样的题，所以还是要检查好几遍。

写到一半想到了一个可能更快的方法，总路程数num，先算出1到10公里的每个费用的最小平均公里费用x，该路程为n，则如果路程数小于num且为n的整数倍，

则最小费用一定是x的整数倍，那么从这个数开始往后做动态规划就会节省很多计算量。

不过对于这题好像没什么必要，可能ACM会追求运行时间最短？