Solution Notes: We transform each landscape pattern into an array of length at most 1000 by listing out the locations of the individual units of dirt in the landscape in order. For example, if we have a landscape with heights 3,1,4,1, we would transform this into the sequence 0,0,0,1,2,2,2,2,3 (e.g., there are 4 units of dirt at position 2). Our problem now reduces to something very close to the computation of the "edit distance" between two sequences, which is a classical dynamic programming problem. Our goal is to transform one landscape sequence into another at minimum cost given three possible operations: insertion of a new character (at cost X), deletion of a character (at cost Y), or modification of a character (at cost Z times the magnitude of the change). This can be accomplished in O(N^2) time (where N=1000) using dynamic programming, as shown below. Each subproblem C[i][j] we solve along the way represents the minimum cost of transforming just the first i characters of the source sequence into just the first j characters of the target sequence.

#include <stdio.h>
#define INF 2000000000
#define MIN(x,y) ((x)<(y) ? (x) : (y))
#define ABS(x) ((x) > 0 ? (x) : -(x))

int A[1001], B[1001], nA, nB;
int C[1001][1001], X, Y, Z;

int main(void)
{
  int i, j, n;
  
  freopen ("landscape.in", "r", stdin);
  freopen ("landscape.out", "w", stdout);

  scanf ("%d %d %d %d", &n, &X, &Y, &Z);
  for (i=0; i<n; i++) {
    scanf ("%d", &j); while (j>0) { A[++nA] = i; j--; } 
    scanf ("%d", &j); while (j>0) { B[++nB] = i; j--; } 
  }
  
  for (j=0; j<=nB; j++) C[0][j] = j*X;
  for (i=0; i<=nA; i++) C[i][0] = i*Y;

  for (i=1; i<=nA; i++)
    for (j=1; j<=nB; j++) {
      C[i][j] = INF;
      C[i][j] = MIN(C[i][j], C[i][j-1] + X);
      C[i][j] = MIN(C[i][j], C[i-1][j] + Y);
      C[i][j] = MIN(C[i][j], C[i-1][j-1] + Z * ABS(A[i]-B[j]));
    }
  
  printf ("%d\n", C[nA][nB]);
  return 0;
}