barica.cpp

Bài toán 

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

typedef pair<ii, int> triple;

#define X first

#define Y second

bool maximize(int &a, int b){ if (a<b) a=b; else return false; return true; }

int n, K;

triple a[1230997];

int c[1230997];

int x_prev[1230997];

int y_prev[1230997];

vector<int> T;

int F[2][2][333000];

int FF[2][2][330000];

int f(int u, bool x_go, bool y_go, bool tracing=false){

    int r=-0x3f3f3f3f, d=0;

    if (u==0) return -0x3f3f3f3f;

    if (u==1) return c[u];

    if (!tracing && FF[x_go][y_go][u]++) return F[x_go][y_go][u];

    if (x_go) if (maximize(r, f(x_prev[u], true, false))) d=1;

    if (y_go) if (maximize(r, f(y_prev[u], false, true))) d=2;

    if (f(x_prev[u], true, false) >= K) if (maximize(r, f(x_prev[u], true, false) - K + c[u])) d=3;

    if (f(y_prev[u], false, true) >= K) if (maximize(r, f(y_prev[u], false, true) - K + c[u])) d=4;

    if (tracing){

        if (d==1) f(x_prev[u], true, false, true);

        if (d==2) f(y_prev[u], false, true, true);

        if (d==3) { f(x_prev[u], true, false, true); T.push_back(u); }

        if (d==4) { f(y_prev[u], false, true, true); T.push_back(u); }

    }

    //printf("f(%d) = %d\n", u, r);

    return F[x_go][y_go][u] = r;

}

bool x_first(triple a, triple b){ return a.X.X==b.X.X ? a<b : a.X.X<b.X.X; }

bool y_first(triple a, triple b){ return a.X.Y==b.X.Y ? a<b : a.X.Y<b.X.Y; }

bool id_first(triple a, triple b){ return a.Y==b.Y ? a<b : a.Y<b.Y; }

main(){

    int i;

    scanf("%d%d", &n, &K);

    for (i=1; i<=n; i++) scanf("%d%d%d", &a[i].X.X, &a[i].X.Y, &c[i]);

    for (i=1; i<=n; i++) a[i].Y=i;

    sort(a+1, a+n+1, x_first);

    for (i=1; i<=n; i++)

    if (i>1 && a[i].X.X==a[i-1].X.X)

    x_prev[a[i].Y]=a[i-1].Y;

    else x_prev[a[i].Y]=0;

    sort(a+1, a+n+1, y_first);

    for (i=1; i<=n; i++)

    if (i>1 && a[i].X.Y==a[i-1].X.Y)

    y_prev[a[i].Y]=a[i-1].Y;

    else y_prev[a[i].Y]=0;

    //for (i=1; i<=n; i++) printf(i==n ? "%d\n": "%d ", x_prev[i]);

    //for (i=1; i<=n; i++) printf(i==n ? "%d\n": "%d ", y_prev[i]);

    sort(a+1, a+n+1, id_first);

    printf("%d\n", f(n, 0, 0));

    T.push_back(1);

    f(n, 0, 0, true);

    printf("%d\n", T.size());

    for (i=0; i<T.size(); i++)

    printf("%d %d\n", a[T[i]].X.X, a[T[i]].X.Y);

}

Nhận xét