BZOJ2734 [HNOI2012]集合选数
BZOJ1223 [HNOI2002]Kathy函数

BZOJ1023 [SHOI2008]cactus仙人掌图

laekov posted @ 2015年3月05日 15:40 in 未分类 with tags bzoj ds dp , 600 阅读

第六百道题一定要不水!虽然离第一页还有几十道题的距离。

 

很早之前见过的题吧。然后一直觉得特别难写所以都没写。以前写点不重复的仙人掌都觉得挺痛苦,更不要说这个了。

 

现在想想还行,因为我yy出了化简的方法。先搞出dfs树。然后一个顶点如果是一个环里深度最浅的,那么称它为这个环的头。可以证明一个顶点最多在一个不以它为头的环上。把这个环记下来,其它的环都从这个顶点去找边来找就行了。这样的话可以比较节省代码量,写起来也比较明了。虽然还是比mhy长。

 

然后因为我在最后一步dp的时候写了一个static的f数组,所以光荣了。debug了好久。晕。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct edge {
	int t, av;
	edge *next, *rv;
};
struct ball {
	int l, *a, h;
};

const int maxn = 50009;
const int maxm = 200009;
const int maxarr = 400009;

int n, m, cb, fb[maxn], d[maxn];
int f[maxn], ans, fd[maxn], fe[maxn];
int stc[maxn], tst;
int ibuf_arr[maxarr], *ibuf(ibuf_arr);
bool vis[maxn];
edge elst[maxm], *ep(elst), *head[maxn];
ball b[maxm];

inline edge* addEdge(int u, int v) {
	ep-> t = v;
	ep-> av = 1;
	ep-> next = head[u];
	return head[u] = ep ++;
}

inline void upMax(int& a, int b) {
	if (a < b)
		a = b;
}

void dfsBall(int p) {
	vis[p] = 1;
	stc[++ tst] = p;
	for (edge *e = head[p]; e; e = e-> next)
		if (e-> av) {
			e-> rv-> av = 0;
			if (vis[e-> t] && (!fb[p])) {
				e-> av = 0;
				b[++ cb]. l = 0;
				b[cb]. a = ibuf;
				for (int i = tst; 1; -- i) {
					b[cb]. a[b[cb]. l ++] = stc[i];
					if (stc[i] != e-> t)
						fb[stc[i]] = cb;
					else
						break;
				}
				b[cb]. h = e-> t;
				ibuf += b[cb]. l;
			}
			else {
				d[e-> t] = d[p] + 1;
				dfsBall(e-> t);
			}
		}
	-- tst;
}

void downDP(int p) {
	fd[p] = fe[p] = 0;
	for (edge* e = head[p]; e; e = e-> next)
		if (e-> av) {
			if (fb[e-> t] && p == b[fb[e-> t]]. h) {
				int bi(fb[e-> t]), fl(0);
				for (int i = 0; i < b[bi]. l; ++ i)
					if (b[bi]. a[i] != b[bi]. h) {
						int q(b[bi]. a[i]);
						downDP(q);
						upMax(fl, fd[q] + min(d[q] - d[p], b[bi]. l - d[q] + d[p]));
					}
				if (fl > fd[p]) {
					fe[p] = fd[p];
					fd[p] = fl;
				}
				else if (fl > fe[p])
					fe[p] = fl;
			}
			else if (!fb[p] || fb[p] != fb[e-> t]) {
				downDP(e-> t);
				int v(fd[e-> t] + 1);
				if (v > fd[p]) {
					fe[p] = fd[p];
					fd[p] = v;
				}
				else if (v > fe[p])
					fe[p] = v;
			}
		}
	upMax(ans, fd[p] + fe[p]);
}

#define modi(_i_) (((_i_)>=b[bi].l)?((_i_)-b[bi].l):(_i_))
void upDP(int p, int u) {
	static int q[maxn << 1], fu[maxn << 1];
	for (edge* e = head[p]; e; e = e-> next)
		if (e-> av) {
			if (fb[e-> t] && p == b[fb[e-> t]]. h) {
				int bi(fb[e-> t]), fl(0);
				int *f(ibuf);
				ibuf += b[bi]. l;
				for (int i = 0; i < b[bi]. l; ++ i) {
					int q(b[bi]. a[i]);
					f[i] = 0;
					if (q == p)
						break;
					fu[i] = fd[q];
					upMax(fl, fd[q] + min(d[q] - d[p], b[bi]. l - d[q] + d[p]));
				}
				if (fl == fd[p])
					fu[b[bi]. l - 1] = max(u, fe[p]);
				else
					fu[b[bi]. l - 1] = max(u, fd[p]);
				int hd(0), tl(1), hl(b[bi]. l >> 1);
				q[0] = 0;
				for (int i = 1; i < (b[bi]. l << 1); ++ i) {
					int fi(modi(i));
					while (hd < tl && i - q[hd] > hl)
						++ hd;
					if (hd < tl)
						upMax(f[fi], fu[modi(q[hd])] + i - q[hd]);
					while (hd < tl && fu[modi(q[tl - 1])] - q[tl - 1] <= fu[fi] - i)
						-- tl;
					q[tl ++] = i;
				}
				hd = 0;
				tl = 1;
				q[0] = (b[bi]. l << 1) - 1;
				for (int i = (b[bi]. l << 1) - 2; i >= 0; -- i) {
					int fi(modi(i));
					while (hd < tl && q[hd] - i > hl)
						++ hd;
					if (hd < tl)
						upMax(f[fi], fu[modi(q[hd])] + q[hd] - i);
					while (hd < tl && fu[modi(q[tl - 1])] + q[tl - 1] <= fu[fi] + i)
						-- tl;
					q[tl ++] = i;
				}
				for (int i = 0; i < b[bi]. l - 1; ++ i) {
					upMax(ans, f[i] + fd[b[bi]. a[i]]);
					upDP(b[bi]. a[i], f[i]);
				}
				ibuf -= b[bi]. l;
			}
			else if (!fb[p] || fb[e-> t] != fb[p]) {
				int v((fd[e-> t] + 1 == fd[p]) ? fe[p] : fd[p]);
				upDP(e-> t, max(u, v) + 1);
			}
		}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &m);
	memset(head, 0, sizeof(head));
	for (int i = 0; i < m; ++ i) {
		int c, u, v;
		scanf("%d%d", &c, &u);
		while (-- c) {
			scanf("%d", &v);
			edge *a(addEdge(u, v)), *b(addEdge(v, u));
			a-> rv = b;
			b-> rv = a;
			u = v;
		}
	}
	memset(vis, 0, sizeof(vis));
	memset(fb, 0, sizeof(fb));
	cb = 0;
	tst = 0;
	d[1] = 1;
	dfsBall(1);
	ans = 0;
	downDP(1);
	upDP(1, 0);
	printf("%d\n", ans);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter