P1177 도로 승차 - Smart Online Judge

간단한 동적 계획
 
제목 ID: 1177
제목: 도로 승차
유효 시간: 15ms
공간 소비량: 516KB
프로그램 코드:

 1 #include<iostream>

 2 using namespace std;

 3 

 4 int f[11];

 5 int g[102];

 6 int main(){

 7     for(int i=1;i<=10;i++){

 8         cin>>f[i];

 9     }

10     for(int i=1;i<=102;i++){

11         g[i]=0;

12     }

13     

14     int a;

15     cin>>a;

16     

17     for(int i=1;i<=a;i++){

18         int min=65536;

19         if(i<=10){

20             for(int j=1;j<=10;j++){

21                 if(i>=j&&(g[i-j]+f[j])<min)

22                     min=g[i-j]+f[j];

23             }

24         }

25         else{

26             for(int j=1;j<i;j++){

27                 if((g[i-j]+g[j])<min)

28                     min=g[i-j]+g[j];

29             }

30         }

31         g[i]=min;

32     //    cout<<g[i]<<" ";

33     }

34 //    cout<<endl;

35 

36     

37     cout<<g[a]<<endl;

38 //    system("pause");

39     return 0;

40 

41 }

 
제목 설명
특별한 일방통행로는 킬로미터마다 정류장이 있다.고객은 그들이 차를 탄 킬로미터에 따라 비용을 지불한다.예를 들어 견본의 첫 번째 줄은 비용의 명세서이다.
10킬로미터를 넘는 차는 한 대도 없고 한 고객은 n킬로미터(1<=n<=100)를 주행할 계획이다. 무한정 차를 갈아타서 여정을 완성할 수 있다.마지막으로 비용이 가장 적게 요구된다.
입력 형식
첫 번째 줄의 10개의 정수는 각각 1~10킬로미터를 걷는 비용(<=500)을 나타낸다.10킬로미터를 주행하는 것이 1킬로미터를 주행하는 것보다 비용이 적을 수 있으니 주의해라.
두 번째 줄의 정수 n은 여행객의 총 노정수를 나타낸다.
출력 형식
최소한의 비용을 표시하는 정수만 있다.
샘플 입력

12 21 31 40 49 58 69 79 90 101

15

샘플 출력

147

데이터 범위 및 프롬프트