JZOI-3598 BUSSES

题目描述

lqp家离学校十分十分远,同时他又没有钱乘taxi。于是他不得不每天早早起床，匆匆赶到公交车站乘车到学校。众所周知CZ是个公交车十分发达的地方，但是CZ的公交车十分的奇怪，lqp到学校的这段路上每一公里就有一公交车站，乘车费用如下表：   公里数 1 2 3 4 5 6 7 8 9 10   费用 12 21 31 40 49 58 69 79 90 101   而一辆汽车从不行驶超过10公里。lqp家距离学校n公里(不会超过100公里)，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比1公里小的情况是允许的）。

输入

输入文件共两行，第一行为10个不超过100的整数，依次表示行驶1～10公里的费用，相邻两数间用空格隔开；第二行为lqp想要行驶的公里数(<=100)。

输出

输出文件仅一行包含一个整数，表示该测试点的最小费用。

样例

输入 12 21 31 40 49 58 69 79 90 101 15 输出  

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#include 
using namespace std;
void p(register int a){
    if(a==1) putchar('\n');
    if(a==2) putchar(' ');
}
void write(register int x){
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
void read(register int &s){
    s=0;
    register bool flag=false;
    register char ch=getchar();
    while(!isdigit(ch)){
    if(ch=='-') flag=true;
    ch=getchar();
    }
    while(isdigit(ch)){
    s=s*10+ch-'0';
    ch=getchar();
    }
    if(flag) s*=-1;
}
int dp[186];
int a[11], n;
int main()
{
    for(int i=1;i<=10;i++)
        read(a[i]);        //快读输入十个数字
    read(n);
    dp[1]=a[1];        //初始状态，走一千米的最小花费即为用走一千米
    for(int i=2;i<=n;i++)
    {
        int mini=inf;
        for(int j=1;j<=min(i, 10)/*为了不要访问到负数组里*/;j++){
            mini=min(a[j]+dp[i-j], mini);        //状态转移方程  dp[i]=min(dp[i-1]+a[1], dp[i-2]+a[2], dp[...]+a[...], dp[i-10]+a[10]  即为这一步可能是之前1, 2, 3，...，10千米之前走过来的，取一个最小值即可
        }
        dp[i]=mini;    //更新这一位的最小值
    }
    cout<