【BZOJ 4200】【UOJ 132】【NOI 2015】園芸師とベテランドライバー
8409 ワード
【タイトルリンク】 BZOJ UOJ
【考え方のポイント】は、すべての点を縦座標で並べ替え、同じ縦座標の点をそれぞれ処理する. は明らかに、各点の各方向の後続点が存在する場合、唯一であり、先に処理される. 記(f_i)は、ノード(i)から最も多く通過できる点数を表す. 左右の移動を考慮しなければ、(f_i)は、(i)が3方向に後続するノードの(f)値の最大値に1を加算し、この値を(tmp_i)と記す. 同じ縦座標の点横座標をインクリメントしてもよいが、(f_i=max{tmp_i,max_{j=1}^{i-1}{tmp_j+N-j+1},max_{j=i+1}^{N}{tmp_j+j}})がある. は明らかに後の2つの部分が前/接尾辞の最大値で転送を最適化することができ、これにより問題の前の2つの質問を解決することができる. は、第3の質問を考慮して、どの辺が前の問題の最適解に現れる可能性があるかを知っていれば、上下境界のあるアクティブな集約最小流によって問題を解決することができ、問題は、どの辺が前の問題の最適解に現れる可能性があるかを判断することである. 再度DP,記(g_i)は、原点から点(i)まで多く経過した点数を表し、原点から到達できなければ(i)、記(g_i=-infty)とする. 左右の移動を考慮しなければ、(g_i)は、(i)が3方向に後続するノードの(f)値の最大値に1を加算し、この値を(tmp_i)と記す. 同じ縦座標の点横座標をインクリメントしてもよいとすると、(g_i=max{tmp_i,max_{j=1}^{i-1}{tmp_j}+i,max_{j=i+1}^{N}{tmp_j}+N-i+1})がある. は、明らかに後の2つの部分が前/接尾辞の最大値で転送を最適化することができる. (g_i)を求めた後、左右方向でないエッジ((x,y))を考慮すると、答えにだまされ、(g_y+f_x=Ans)のみが現れる. これで、問題は解決された.時間複雑度(O(NlogN+Dinic(N,N)).
【コード】
【考え方のポイント】
【コード】
#include
using namespace std;
const int MAXN = 50005;
const int MAXP = 50005;
const int INF = 1e8;
template void chkmax(T &x, T y) {x = max(x, y); }
template void chkmin(T &x, T y) {x = min(x, y); }
template void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template void writeln(T x) {
write(x);
puts("");
}
struct info {int x, y, home; };
struct edge {int dest; int flow; unsigned home; };
int s, t, olds, oldt, dist[MAXP];
vector b[MAXP]; unsigned curr[MAXP];
bool cmp(info a, info b) {
if (a.y == b.y) return a.x < b.x;
else return a.y > b.y;
}
info a[MAXN];
map up, lup, rup;
int nxtup[MAXN], nxtlup[MAXN], nxtrup[MAXN];
int tmp[MAXN], ans[MAXN], method[MAXN], tot;
int tnp[MAXN], bns[MAXN];
int dinic(int pos, int limit) {
if (pos == t) return limit;
int used = 0, tmp;
for (unsigned &i = curr[pos]; i < b[pos].size(); i++)
if (b[pos][i].flow != 0 && dist[pos] + 1 == dist[b[pos][i].dest] && (tmp = dinic(b[pos][i].dest, min(limit - used, b[pos][i].flow))) != 0) {
used += tmp;
b[pos][i].flow -= tmp;
b[b[pos][i].dest][b[pos][i].home].flow += tmp;
if (used == limit) return used;
}
return used;
}
bool bfs() {
static int q[MAXP], l = 0, r = -1;
for (int i = 0; i <= r; i++)
dist[q[i]] = 0;
q[l = r = 0] = s, dist[s] = 1;
while (l <= r) {
int tmp = q[l++];
for (unsigned i = 0; i < b[tmp].size(); i++)
if (b[tmp][i].flow != 0 && dist[b[tmp][i].dest] == 0) {
q[++r] = b[tmp][i].dest;
dist[b[tmp][i].dest] = dist[tmp] + 1;
}
}
return dist[t] != 0;
}
void addedge(int s, int t, int flow) {
b[s].push_back((edge) {t, flow, b[t].size()});
b[t].push_back((edge) {s, 0, b[s].size() - 1});
}
void addedge(int x, int y) {
addedge(x, y, INF);
addedge(s, y, 1);
addedge(x, t, 1);
}
int main() {
int n; read(n);
for (int i = 1; i <= n; i++)
read(a[i].x), read(a[i].y), a[i].home = i;
sort(a + 1, a + n + 1, cmp);
int last = 0;
for (int i = 1; i <= n; i++) {
if (a[i].y == a[i + 1].y) continue;
for (int j = last + 1; j <= i; j++) {
tmp[j] = 0;
if (up.count(a[j].x)) chkmax(tmp[j], up[a[j].x]);
if (lup.count(a[j].x + a[j].y)) chkmax(tmp[j], lup[a[j].x + a[j].y]);
if (rup.count(a[j].x - a[j].y)) chkmax(tmp[j], rup[a[j].x - a[j].y]);
}
static int pre[MAXN], suf[MAXN];
pre[last] = suf[i + 1] = -INF;
for (int j = last + 1; j <= i; j++)
pre[j] = max(pre[j - 1], tmp[j] - j);
for (int j = i; j >= last + 1; j--)
suf[j] = max(suf[j + 1], tmp[j] + j);
for (int j = last + 1; j <= i; j++) {
ans[j] = tmp[j];
chkmax(ans[j], pre[j - 1] + i);
chkmax(ans[j], suf[j + 1] - (last + 1));
ans[j] += 1;
up[a[j].x] = ans[j];
lup[a[j].x + a[j].y] = ans[j];
rup[a[j].x - a[j].y] = ans[j];
}
last = i;
}
int ansval = 0;
if (up.count(0)) chkmax(ansval, up[0]);
if (lup.count(0)) chkmax(ansval, lup[0]);
if (rup.count(0)) chkmax(ansval, rup[0]);
writeln(ans[0] = ansval);
up.clear(), lup.clear(), rup.clear();
last = 0;
for (int i = 1; i <= n; i++) {
if (a[i].y == a[i + 1].y) continue;
for (int j = last + 1; j <= i; j++) {
if (up.count(a[j].x)) nxtup[j] = up[a[j].x];
if (lup.count(a[j].x + a[j].y)) nxtlup[j] = lup[a[j].x + a[j].y];
if (rup.count(a[j].x - a[j].y)) nxtrup[j] = rup[a[j].x - a[j].y];
up[a[j].x] = j;
lup[a[j].x + a[j].y] = j;
rup[a[j].x - a[j].y] = j;
}
last = i;
}
nxtup[0] = up[0];
nxtlup[0] = lup[0];
nxtrup[0] = rup[0];
int now = 0;
if (nxtup[0] && ans[nxtup[0]] == ansval) now = nxtup[0];
else if (nxtlup[0] && ans[nxtlup[0]] == ansval) now = nxtlup[0];
else if (nxtrup[0] && ans[nxtrup[0]] == ansval) now = nxtrup[0];
while (now != 0) {
int l = now, r = now;
while (a[l - 1].y == a[now].y) l--;
while (a[r + 1].y == a[now].y) r++;
static int pre[MAXN], suf[MAXN];
pre[l - 1] = suf[r + 1] = -INF;
for (int i = l; i <= r; i++)
pre[i] = max(pre[i - 1], tmp[i] - i);
for (int i = r; i >= l; i--)
suf[i] = max(suf[i + 1], tmp[i] + i);
int tans = tmp[now];
chkmax(tans, pre[now - 1] + r);
chkmax(tans, suf[now + 1] - l);
if (tans == tmp[now]) {
method[++tot] = a[now].home;
if (ans[nxtup[now]] == tmp[now]) now = nxtup[now];
else if (ans[nxtlup[now]] == tmp[now]) now = nxtlup[now];
else if (ans[nxtrup[now]] == tmp[now]) now = nxtrup[now];
else now = 0;
} else if (tans == pre[now - 1] + r) {
for (int i = now; i <= r; i++)
method[++tot] = a[i].home;
for (int i = now - 1; i >= l; i--) {
method[++tot] = a[i].home;
if (tans == tmp[i] - i + r) {
if (ans[nxtup[i]] == tmp[i]) now = nxtup[i];
else if (ans[nxtlup[i]] == tmp[i]) now = nxtlup[i];
else if (ans[nxtrup[i]] == tmp[i]) now = nxtrup[i];
else now = 0;
break;
}
}
} else {
for (int i = now; i >= l; i--)
method[++tot] = a[i].home;
for (int i = now + 1; i <= r; i++) {
method[++tot] = a[i].home;
if (tans == tmp[i] + i - l) {
if (ans[nxtup[i]] == tmp[i]) now = nxtup[i];
else if (ans[nxtlup[i]] == tmp[i]) now = nxtlup[i];
else if (ans[nxtrup[i]] == tmp[i]) now = nxtrup[i];
else now = 0;
break;
}
}
}
}
for (int i = 1; i <= tot; i++)
printf("%d ", method[i]);
printf("
");
up.clear(), lup.clear(), rup.clear();
up[0] = lup[0] = rup[0] = 0;
last = n + 1;
for (int i = n; i >= 1; i--) {
if (a[i].y == a[i - 1].y) continue;
int l = i, r = last - 1;
for (int j = l; j <= r; j++) {
tnp[j] = -INF;
if (up.count(a[j].x)) chkmax(tnp[j], up[a[j].x]);
if (lup.count(a[j].x + a[j].y)) chkmax(tnp[j], lup[a[j].x + a[j].y]);
if (rup.count(a[j].x - a[j].y)) chkmax(tnp[j], rup[a[j].x - a[j].y]);
}
static int pre[MAXN], suf[MAXN];
pre[l - 1] = suf[r + 1] = -INF;
for (int j = l; j <= r; j++)
pre[j] = max(pre[j - 1], tnp[j]);
for (int j = r; j >= l; j--)
suf[j] = max(suf[j + 1], tnp[j]);
for (int j = l; j <= r; j++) {
bns[j] = tnp[j];
chkmax(bns[j], pre[j - 1] + j - l);
chkmax(bns[j], suf[j + 1] + r - j);
bns[j] += 1;
up[a[j].x] = bns[j];
lup[a[j].x + a[j].y] = bns[j];
rup[a[j].x - a[j].y] = bns[j];
}
last = i;
}
s = n + 1, t = n + 2;
olds = n + 3, oldt = n + 4;
for (int i = 0; i <= n; i++) {
int nxt = nxtup[i];
if (ans[nxt] + bns[i] == ansval) addedge(a[i].home, a[nxt].home);
nxt = nxtlup[i];
if (ans[nxt] + bns[i] == ansval) addedge(a[i].home, a[nxt].home);
nxt = nxtrup[i];
if (ans[nxt] + bns[i] == ansval) addedge(a[i].home, a[nxt].home);
}
for (int i = 0; i <= n; i++) {
addedge(olds, i, INF);
addedge(i, oldt, INF);
}
while (bfs()) {
memset(curr, 0, sizeof(curr));
dinic(s, INF);
}
addedge(oldt, olds, INF);
int finalans = 0;
while (bfs()) {
memset(curr, 0, sizeof(curr));
finalans += dinic(s, INF);
}
writeln(finalans);
return 0;
}