Cod sursa(job #51344)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 11 aprilie 2007 13:50:41
Problema Popandai Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#define NMAX 2510
#define MIN(a,b) (((a)<(b))?(a):(b))
#define INF 2147483640

int N, B[NMAX], E[NMAX], T[3], A[NMAX][NMAX], M[NMAX];

int main()
{
        int i, j, b, e;

        freopen("log.in", "r", stdin);
        scanf("%d", &N);
        for (i = 0; i < 3; i++) scanf("%d", &T[i]);

        for (i = 1; i <= N; i++) scanf("%d %d", &B[i], &E[i]);

        for (i = 0; i <= N+1; i++)
            for (j = 0; j <= N+1; j++) A[i][j] = INF;

        A[1][0] = T[2]*(B[1]-E[1])*(B[1]-E[1]);
        M[1] = A[1][0];
        for (i = 2; i <= N; i++)
        {
            b = B[i]; e = E[i];
            A[i][0] = T[2]*(b-e)*(b-e)+M[i-1]+T[0];
            M[i] = A[i][0];
            for (j = i-1; j > 0; j--)
                if (b == E[j])
                {
                        b = B[j];
                        A[i][i-j] = M[j-1]+T[1]+T[2]*(b-e)*(b-e)+T[0];
                        M[i] = MIN(M[i], A[i][i-j]);
                }
        }

        freopen("log.out", "w", stdout);
        printf("%d\n", M[N]);

        return 0;
        
}