1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include "iostream" #include "algorithm" #include "cstring" #include "cstdio" #include "cmath" #include "vector" #include "map" #include "set" #include "queue" using namespace std; #define MAXN 5006
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i) #define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i) #define pii pair<int,int> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back #define vi vector<int> #define all(x) (x).begin() , (x).end() #define mem( a ) memset( a , 0 , sizeof a ) typedef long long ll; int n , s , e; ll dp[MAXN][MAXN]; int A[MAXN] , B[MAXN] , C[MAXN] , D[MAXN] , x[MAXN];
void solve() { cin >> n >> s >> e; rep( i , 1 , n ) scanf("%d",x + i); rep( i , 1 , n ) scanf("%d",A + i); rep( i , 1 , n ) scanf("%d",B + i); rep( i , 1 , n ) scanf("%d",C + i); rep( i , 1 , n ) scanf("%d",D + i); memset( dp , 0x3f , sizeof dp ); dp[1][1] = ( s != 1 ? B[1] - x[1] : 0 ) + ( e != 1 ? D[1] - x[1] : 0 ); rep( i , 2 , n - 1 ) { if( i != s && i != e ) { rep( j , ( i > s && i > e ? 2 : 1 ) , i ) { if( i <= s || j != 1 ) dp[i][j] = min( dp[i][j] , dp[i - 1][j] + B[i] + C[i] ); if( i <= e || j != 1 ) dp[i][j] = min( dp[i][j] , dp[i - 1][j] + A[i] + D[i] ); dp[i][j + 1] = min( dp[i][j + 1] , dp[i - 1][j] + B[i] - x[i] + D[i] - x[i] ); if( j != 1 ) dp[i][j - 1] = min( dp[i][j - 1] , dp[i - 1][j] + A[i] + x[i] + C[i] + x[i] ); } } else if( i == s ) { rep( j , 1 , i ) { dp[i][j] = min( dp[i][j] , dp[i - 1][j] + C[i] + x[i] ); dp[i][j + 1] = min( dp[i][j + 1] , dp[i - 1][j] + D[i] - x[i] ); } } else if( i == e ) { rep( j , 1 , i ) { dp[i][j + 1] = min( dp[i][j + 1] , dp[i - 1][j] + B[i] - x[i] ); dp[i][j] = min( dp[i][j] , dp[i - 1][j] + A[i] + x[i] ); } } }
ll res = 0;
res = dp[n - 1][1 + ( s != n && e != n )] + ( s != n ? A[n] + x[n] : 0 ) + ( e != n ? C[n] + x[n] : 0 ); cout << res << endl; }
signed main() {
solve(); }
|