首页 > 代码库 > bzoj 1023: [SHOI2008]cactus仙人掌图
bzoj 1023: [SHOI2008]cactus仙人掌图
这道题是我做的第一道仙人掌DP，小小纪念一下……
仙人掌DP就是环上的点环状DP，树上的点树上DP。就是说，做一遍DFS，DFS的过程中处理出环，环上的点先不DP，先把这些换上的点的后继点都处理出来，再从环上DFS序最小的点开始进行环状DP，就ok了。但是注意判断是不是父边不能用 v[k] != fa[now]，这样如果两个点构成一个环就会出错，所以存这个点的父边，记为fb[now]，这样判断的时候只需判断(k^1) != fb[now]，就可以了。在环状DP的时候我想了很久怎么用单调队列优化（其实是我太弱了，环状DP都不会写=_=）。存一个p[i] = f[i]-i，然后用 f[i]+i+p[j] 更新答案就可以了，最后只需更新环最顶端的点的 f 值而不用全部修改。
这么说很笼统，还是看代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <stack>#define N 500100#define M 1001000using namespace std; int n, m;int p[N], next[M], v[M], bnum = -1;int f[N] = {0};int ans = 0; void addbian(int x, int y){ bnum++; next[bnum] = p[x]; p[x] = bnum; v[bnum] = y; bnum++; next[bnum] = p[y]; p[y] = bnum; v[bnum] = x;} int nowtime = 0;int low[N], vist[N] = {0}, fb[N], fa[N];bool instack[N] = {0}; int roop[N], roopnum; struct ss{ int place, val;}dui[N];int head, tail; void work_circle(){ int limit = roopnum/2; for (int i = roopnum+1; i <= (roopnum<<1); ++i) roop[i] = roop[i-roopnum]; ss x; x.val = f[roop[1]]-1; x.place = 1; head = 1; tail = 1; dui[head] = x; for (int i = 2; i <= (roopnum<<1); ++i) { while (dui[head].place+limit < i) head++; ans = max(ans, f[roop[i]]+i+dui[head].val); x.val = f[roop[i]]-i; x.place = i; while (dui[tail].val < x.val && tail >= head) tail--; dui[++tail] = x; }} void dfs(int now){ int k = p[now]; vist[now] = ++nowtime; low[now] = vist[now]; while (k != -1) { if (k != fb[now]) { if (vist[v[k]]) low[now] = min(low[now], vist[v[k]]); else { fa[v[k]] = now; fb[v[k]] = k^1; dfs(v[k]); low[now] = min(low[now], low[v[k]]); } } k = next[k]; } k = p[now]; while (k != -1) { if ((k^1) == fb[v[k]] && low[v[k]] > vist[now]) { ans = max(ans, f[now] + f[v[k]] + 1); f[now] = max(f[now], f[v[k]] + 1); } if ((k^1) != fb[v[k]] && vist[now] < vist[v[k]]) { roopnum = 0; int x = v[k]; while (x != fa[now]) { roop[++roopnum] = x; x = fa[x]; } work_circle(); for (int i = 1; i < roopnum; ++i) f[now] = max(f[now], f[roop[i]]+min(i, roopnum-i)); } k = next[k]; }} int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) p[i] = -1; for (int i = 1; i <= m; ++i) { int k, x, y; scanf("%d%d", &k, &x); for (int j = 1; j < k; ++j) { scanf("%d", &y); addbian(x, y); x = y; } } fa[1] = 0; fb[1] = -1; dfs(1); printf("%d\n", ans); return 0;}
bzoj 1023: [SHOI2008]cactus仙人掌图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。