車代(完全バックパック)

824 ワード

特別な一方通行街には1キロごとにバス停があります.お客様は彼らが車に乗るキロの使用料によって料金を払います.例えば、次の表は費用のリストです.10キロを超える車は1台もなく、1人の顧客がnキロ(1<=n<=100)を走るつもりで、無限の乗り換えで旅を終えることができます.最後に要求費用が最も少ないです.
入力形式:
1行目の10個の整数はそれぞれ1~10キロの費用(<=500)を表す.これらの数は実際の経済的意義がなく、10キロの費用が1キロより少ない可能性があることに注意する.
2行目の整数nは、旅客の総行程数を表す.
入力形式:
最小費用は整数のみです.
サンプル入力
12 21 31 40 49 58 69 79 90 101
15

サンプル出力
147

#include
using namespace std; int main(){const int int INF=0 x 3 f 3 f 3 f 3 f;int f[101];//i kmを走行する最小費用int c[11];//i kmを走行する通話料int n;for(int i=1;i<=10;i++)cin>>c[i];cin>>n>>>n;f[0]=0;for(int i=1;i<=100;i++)f[i]=100;i+++)f[i]=INF;for(int i=1;i<=10;i++){for(int j=1;j<=1;j<=n;j++){ifif(j(j>====n;j+){if(j(j>==i)f[j]=min(f[j],f[j-i]+c[i]);}}cout< }