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