luogu 2478 [SDOI2010]城市规划仙人掌上dp.

LINK：城市规划

以前ls 让写的时候由于看不懂题目+以为在图中的环上dp非常困难所以放弃治疗了。

现在终于能把题目看懂了泪目...

题目其实就是在说给出一张图这个有一个非常好的性质满足每个点都最多存在于一个无向边组成的环中。

这种图可以称之为仙人掌但是比仙人掌的性质还要好不仅只满足每条边最多在一个环中每个点也在一个环中。

题目是想让在图中占领一些点使得其周围的点都不能再被占领且这些点的相邻点也不能被占领。

比独立集的要求要严格一点。每个点都有权值求使得占领点的权值和最大值。

还是考虑dp.

f[i][j]表示以i这个点0自己没被占领儿子也没被占领 1表示自己被占领了 2表示儿子被占领的最大值.

考虑在环上的时候发现和其他环外部的点没有任何影响所以直接在换上dp即可。

考虑如果是仙人掌上呢可以发现和这种图情况一模一样不过把一个点下方吊的环变成了点罢了。

所以可以发现这种dp适用于仙人掌图而不仅限于题中给的条件。

没想到这道题还挺奇葩转移没有想象中那么简单。

考虑f[x][2]的转移发现只能有一个儿子占且这个儿子在转移的时候还可以轮换。

这在环上dp的时候是要分类讨论一大堆的。

但是题解区给出了一个非常简明的分类讨论。

设calc(l,r)表示l和r都不选的最大值这个东西也很好做然后依靠这个东西我们可以很简便的分类讨论出来很多东西。

这里我强行使用了题目中的性质这个代码并不适用于仙人掌图如果想的话可以加以修改得以适应。

const int MAXN=1000010;

int n,m,top,len,cnt,sum,ans;

int f[MAXN][3],g[MAXN][3],v[MAXN];

int a[MAXN],dfn[MAXN],b[MAXN],s[MAXN],low[MAXN],w[MAXN];

int lin[MAXN],ver[MAXN<<2],nex[MAXN<<2];

inline void add(int x,int y)

{

	ver[++len]=y;

	nex[len]=lin[x];

	lin[x]=len;

}

inline int calc(int l,int r)//l 和 r 不能选的最大值.

{

	if(l>r)return 0;

	g[l-1][0]=-INF;g[l-1][1]=g[l-1][2]=0;

	rep(l,r,i)

	{

		g[i][0]=max(g[i-1][0],g[i-1][2])+f[b[i]][0];

		g[i][1]=f[b[i]][1]+g[i-1][0];

		g[i][2]=max(f[b[i]][0]+g[i-1][1],f[b[i]][2]+max(g[i-1][0],g[i-1][2]));

	}

	return max(g[r][0],g[r][2]);

}

inline void solve(int x)//处理环

{

	f[x][2]=max(f[x][2]+calc(2,sum),f[x][0]+f[b[2]][1]+f[b[3]][0]+calc(4,sum));

	f[x][2]=max(f[x][2],f[x][0]+f[b[sum]][1]+f[b[sum-1]][0]+calc(2,sum-2));

	f[x][1]=f[x][1]+f[b[2]][0]+f[b[sum]][0]+calc(3,sum-1);//calc(3,sum-1);

	f[x][0]+=calc(2,sum);

}

inline void dfs(int x,int fa)

{

	dfn[x]=low[x]=++cnt;v[x]=fa;

	s[++top]=x;f[x][1]=a[x];

	int ww=0,cc=0;

	go(x)

	{

		if(!dfn[tn])

		{

			dfs(tn,x);

			low[x]=min(low[x],low[tn]);

			if(low[tn]==dfn[x])cc=tn;

			if(low[tn]>dfn[x])

			{

				f[x][0]+=max(f[tn][0],f[tn][2]);

				f[x][1]+=f[tn][0];

				ww=max(ww,f[tn][1]-max(f[tn][0],f[tn][2]));

			}

		}else if(v[x]!=tn)low[x]=min(low[x],dfn[tn]);

	}

	f[x][2]=f[x][0]+ww;

	if(cc)

	{

		int y=0;sum=0;

		b[++sum]=x;

		while(y!=cc)

		{

			y=s[top--];

			b[++sum]=y;

		}

		solve(x);

	}

	if(low[x]>dfn[v[x]])--top;

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(m);

	rep(1,n,i)get(a[i]);

	rep(1,m,i){int get(x);int get(y);add(x,y);add(y,x);}

	rep(1,n,i)if(!dfn[i])dfs(i,0),ans+=max(f[i][0],max(f[i][1],f[i][2]));

	put(ans);return 0;

}

环上分类讨论dp好题~!

巴特西

luogu 2478 [SDOI2010]城市规划仙人掌上dp.

最新文章

热门文章

巴特西

luogu 2478 [SDOI2010]城市规划 仙人掌上dp.

最新文章

热门文章

luogu 2478 [SDOI2010]城市规划仙人掌上dp.