2015年3月27日 星期五

2015/03/27 TIOJ 1842 . 王八 Wombats

// http://tioj.ck.tp.edu.tw/problems/1842
#include <iostream>
#include <cstdio>

using namespace std;

int N, M;
int H[5050][201];
int V[5050][201];

#define INF 2000000000

struct Node
{
    Node *l, *r;
    int DP[201][201];

    Node(){  l = r = NULL;  }
};

Node tmp[50]; int clk = 0;
 int mi = 0;

void pull(Node *O)
{
    int mid[201][201];

    for(int Mi = 0; Mi < M; Mi++)
        for(int Mj = 0; Mj < M; Mj++)
            O->DP[Mi][Mj] = INF;

    for(int Mi = 0; Mi < M; Mi++)
        for(int Mj = 0; Mj < M; Mj++)
        {
            int p = O->l->DP[Mi][Mj]+O->r->DP[Mj][Mi];

            if( p < O->DP[Mi][Mi] )
            {
                O->DP[Mi][Mi] = p;
                mid[Mi][Mi] = Mj;
            }
        }

    for(int Ki = 1; Ki < M; Ki++)
    {
        for(int Mi = 0; Mi+Ki < M; Mi++)
        {
            for(int Mj = mid[Mi][Mi+Ki-1]; Mj <= mid[Mi+1][Mi+Ki]; Mj++)
            {
                int p = O->l->DP[Mi][Mj]+O->r->DP[Mj][Mi+Ki];

                if( p < O->DP[Mi][Mi+Ki] )
                {
                    O->DP[Mi][Mi+Ki] = p;
                    mid[Mi][Mi+Ki] = Mj;
                }
            }
        }

        for(int Mi = M-1; Mi-Ki >= 0; Mi--)
        {
            for(int Mj = mid[Mi-1][Mi-Ki]; Mj <= mid[Mi][Mi-Ki+1]; Mj++)
            {
                int p = O->l->DP[Mi][Mj]+O->r->DP[Mj][Mi-Ki];

                if( p < O->DP[Mi][Mi-Ki] )
                {
                    O->DP[Mi][Mi-Ki] = p;
                    mid[Mi][Mi-Ki] = Mj;
                }
            }
        }
    }

}

void build(Node *&O, int L, int R)
{
    if( !O ) O = new Node();

    if( R-L < 15 )
    {
        int mem[201][201] = {0};

        for(int Li = L; Li < R; Li++)
        {

            for(int Mi = 0; Mi < M; Mi++)
            {
                O->DP[Mi][Mi] = mem[Mi][Mi]+V[Li][Mi];

                for(int Mj = Mi+1, now = 0; Mj < M; Mj++)
                {
                    now += H[Li][Mj-1];
                    if( Li == L ) O->DP[Mi][Mj] = now+V[Li][Mj];
                    else O->DP[Mi][Mj] = mem[Mi][Mj]+V[Li][Mj];
                }

                for(int Mj = Mi-1, now = 0; Mj >= 0; Mj--)
                {
                    now += H[Li][Mj];
                    if( Li == L ) O->DP[Mi][Mj] = now+V[Li][Mj];
                    else O->DP[Mi][Mj] = mem[Mi][Mj]+V[Li][Mj];
                }

                for(int Mj = M-2; Mj >= 0; Mj--)
                    O->DP[Mi][Mj] = min(O->DP[Mi][Mj], O->DP[Mi][Mj+1]+H[Li+1][Mj]);

                for(int Mj = 1; Mj < M; Mj++)
                    O->DP[Mi][Mj] = min(O->DP[Mi][Mj], O->DP[Mi][Mj-1]+H[Li+1][Mj-1]);
            }

            for(int Mi = 0; Mi < M; Mi++)
                for(int Mj = 0; Mj < M; Mj++)
                    mem[Mi][Mj] = O->DP[Mi][Mj];

        }
    }
    else
    {
        build(O->l, L, (L+R)/2);
        build(O->r, (L+R)/2, R);

        pull(O);
    }

}

void update(Node *&O, int L, int R, int A, int B)
{
    if( R-L < 15 ) build(O, L, R);
    else if( B <= L || R <= A ) return;
    else
    {
        int p = clk;

        update(O->l, L, (L+R)/2, A, B);
        update(O->r, (L+R)/2, R, A, B);

        pull(O);
    }
}

Node *root;
int E;

int main()
{
    scanf("%d %d", &N, &M);

    for(int Ni = 0; Ni < N; Ni++)
        for(int Mi = 0; Mi < M-1; Mi++)
            scanf("%d", &H[Ni][Mi]);

    for(int Ni = 0; Ni < N-1; Ni++)
        for(int Mi = 0; Mi < M; Mi++)
            scanf("%d", &V[Ni][Mi]);

    build(root, 0, N-1);

    scanf("%d", &E);

    for(int Ei = 0; Ei < E; Ei++)
    {
        int sp;
        scanf("%d", &sp);

        if( sp == 1 )
        {
            int P, Q, W;
            scanf("%d %d %d", &P, &Q, &W);

            H[P][Q] = W;

            if( P ) update(root, 0, N-1, P-1, P+1);
            else update(root, 0, N-1, P, P+1);
        }
        if( sp == 2 )
        {
            int P, Q, W;
            scanf("%d %d %d", &P, &Q, &W);

            V[P][Q] = W;
            update(root, 0, N-1, P, P+1);
        }
        if( sp == 3 )
        {
            int v1, v2;
            scanf("%d %d", &v1, &v2);

            printf("%d\n", root->DP[v1][v2]);
        }
    }
}

沒有留言:

張貼留言