1031.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//dp
//Hint: start station number can be greater than end station number
//almost TLE....
#include <iostream>
using namespace std;
typedef long long int64;
const int maxN = 10000;
const int maxint = 0x0f0f0f0f;
int64 a[maxN + 1];
int64 f[maxN + 1];
int64 l1, l2, l3, c1, c2, c3;
unsigned  int n , start , end;

void swap(int &x, int &y)
{
     int t = x;
     x = y;
     y = t;
}
void readIn()
{
     int i,j;
     cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3;
     cin >> n;
     cin >> start >> end;
     if( start > end ) swap(start,end);
     for( i = 2 ; i <= n; i++ )
     {
          cin >> a[i];
     }
}

void work()
{
     int i, j;
     memset(f, 15, sizeof(f) );
     f[start] = 0;
     for( i = start; i <= end; i++ )
     {
          for( j = i + 1; j <= end; j++ )
               if( a[j] - a[i] == 0 )
                   f[j] = min(f[j], f[i]);
               else if( a[j] - a[i] <= l1 )
                   f[j] = min(f[j], f[i] + c1);
               else if( a[j] - a[i] <= l2 )
                   f[j] = min(f[j], f[i] + c2);
               else if( a[j] - a[i] <= l3 )
                  f[j] = min(f[j], f[i] + c3); 
               else break;
     }
}
int main()
{
    readIn();
    work();
    cout << f[end] << endl;
    return 0;
}