首页 > 代码库 > 1040: [ZJOI2008]骑士
1040: [ZJOI2008]骑士
首先是因为想学仙人掌图才来先拿这题热热身，结果&……竟然调了一个晚上我的傻叉！（其中一大半的时候是在郁闷hzwer和Greens的代码画风不一样，后来才发现一个用拓扑一个用树dp23333，以后代码坚决自己解决）
贴一下hzwer大神的题解吧：http://hzwer.com/1729.html
以及云的代码：http://hi.baidu.com/greencloud/archive/tag/dp?page=4
treedp：
首先我们发现一个骑士只会觉得另一个骑士丑（233），然后我们想到了树，因为树上每个点只有一个入度，所以边建为从被讨厌的人指向讨厌他的。但是会出现环的情况……这时候一定是在树根那里有个环！（画图就可以发现一定是这样，如果不是在树根那么就会有出现入度为2的情况，显然不可能……)。然后就先处理出不再环上的每个点与各自的子树的情况（dp[x,0]表示x取，dp[x,1]，表示x不取），由于树上只有一个环，so那些环上的点的儿子们如果不再环上那子树一定是棵树不会出现环，so是可以用treedp递归处理出来。（然后拓扑的方法就相反啦，边是从某个人指向这个人讨厌的人，那么那些入度为0的点就是老好人，然后从这些老好人开始推，找老好人讨厌的人&……算过去）
然后就是处理环上怎么取最大的问题啦。
破环成链，这时候就先不考虑链头与链尾不能同时取的情况，跑一边dp，然后再来考虑链头和链尾的限制，也就是链头取的时候链尾不能取，链头不取的时候链尾可取可不取……
（我X我最近什么鬼状态！！！连傻叉题都不会写了）
type arr=record toward,next:longint; end;const maxn=1002333;var edge:array[0..maxn]of arr; first,fa,link,from:array[0..maxn]of longint; value:array[0..maxn]of int64; chose:array[0..maxn]of boolean; dp:array[0..maxn,0..1]of int64; f:array[0..maxn,1..4]of int64; n,m,tot:longint;function max(x,y:int64):int64;begin if x<y then exit(y); exit(x);end;procedure addedge(j,k:longint);begin inc(tot); edge[tot].toward:=k; edge[tot].next:=first[j]; first[j]:=tot;end;procedure treedp(x:longint);var i,too:longint;begin dp[x,1]:=value[x]; dp[x,0]:=0; chose[x]:=false; i:=first[x]; while i>0 do begin too:=edge[i].toward; treedp(too); dp[x,0]:=dp[x,0]+max(dp[too,0],dp[too,1]); dp[x,1]:=dp[x,1]+dp[too,0]; i:=edge[i].next; end;end;procedure into;var i,j:longint;begin readln(n); for i:=1 to n do begin chose[i]:=true; read(value[i],j); addedge(j,i); fa[i]:=j; end;end;procedure work;var i,j,x,now,sum,too:longint; ans,answer:int64;begin answer:=0; for i:=1 to n do if chose[i] then begin sum:=0; x:=i; while chose[x] do begin chose[x]:=false; x:=fa[x]; //from[fa[x]]:=x; from[fa[x]]:=x; end; now:=x; repeat j:=first[x]; dp[x,1]:=value[x]; while j>0 do begin too:=edge[j].toward; if too<>from[x] then begin treedp(too); dp[x,0]:=dp[x,0]+max(dp[too,0],dp[too,1]); dp[x,1]:=dp[x,1]+dp[too,0]; end; j:=edge[j].next; end; inc(sum); link[sum]:=x; x:=fa[x]; until x=now; ans:=0; f[1,1]:=dp[link[1],0]; f[1,2]:=dp[link[1],1]; f[1,3]:=dp[link[1],0]; f[1,4]:=dp[link[1],0]; for j:=2 to sum do begin x:=link[j]; f[j,1]:=max(f[j-1,1],f[j-1,2])+dp[x,0]; f[j,2]:=f[j-1,1]+dp[x,1]; f[j,3]:=max(f[j-1,3],f[j-1,4])+dp[x,0]; f[j,4]:=f[j-1,3]+dp[x,1]; end; ans:=max(f[sum,1],f[sum,3]); ans:=max(ans,f[sum,4]); answer:=answer+ans; end; writeln(answer);end;begin into; work;end.
1040: [ZJOI2008]骑士
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。