***牛客網--最小費用

テーマはある路線の上でN個の駅があって、3種類の距離の道のりがあって、L 1、L 2、L 3、対応する価格はC 1、C 2、C 3です.その対応関係は以下の通りである:距離s運賃09,09.2つのステーション間の距離はL 3を超えない.乗客が移動する2つの駅の距離がL 3より大きい場合、中間の1つの駅から降りて切符を買って乗車することができるので、乗客は全過程で少なくとも2枚の切符を買うことができます.L 1,L 2,L 3,C 1,C 2,C 3をあげます.次に、乗客の旅の開始駅と終点駅であるA Bの値である.次に、N,Nをその路線の合計駅数として入力し、N−1個の整数を入力し、その路線の最初の駅から2番目の駅、3番目の駅、・・・、N番目の駅までの距離を表す.入力により、乗客がAからB駅までの最小費用を出力する.入力記述:L 1 L 2 L 3 C 1 C 2 C 3 A B N a[2]a[3]......a[N]出力記述:複数組のテストデータがある可能性があり、各組のデータに対して、入力に応じて乗客のAからB駅までの最小費用を出力する.
コード:ダイナミックプランニングの問題

//  ：dp（    ），      
//S（n）=O(n*n)
//  ：1.  ticket              
//      2.         i    
//      3.   for  i A+1   B
//            for  ，j A     i  ，  i       j   
//           j              


#include
using namespace std;
int L1,L2,L3,C1,C2,C3;
int A,B;//           
int N;//           
//       
int ticket(int dis)
{
         if(dis<=L1)  return C1;
         else if(dis<=L2)  return C2;
         else return C3;
}
int main()
{
         while(cin>>L1>>L2>>L3>>C1>>C2>>C3)
         {
                  cin>>A>>B>>N;
                  int a[N],cost[N];//         i         
                                   //               
                  for(int i=2;i<=N;i++)  cin>>a[i];
                  a[1]=0;
                  cost[A]=0;//            0，A     ，   0
                  //         
                  //    A     ，  B ，           
                  for(int i=A+1;i<=B;i++)
                  {
                           cost[i]=cost[i-1]+ticket(a[i]-a[i-1]);

                           //    ：j A   ，         L3  （  L3）
                           //      
                           for(int j=A;jcost[j]+ticket(a[i]-a[j])&&(a[i]-a[j])<=L3)
                                    {

                                             cost[i]=cost[j]+ticket(a[i]-a[j]);
                                    }
                           }

                  }
                  cout<