記憶化搜索,f[u,k]表示到節(jié)點(diǎn)u時,剩下k次失控的機(jī)會,所能得到的最大快樂值.
f[u,k]=max{f[v,k]+w[u,v]}
f[u,k]=min(f[u,k],f[v,k-1]+w[u,v]) (v是u的兒子)

?

/************************************************************** Problem: 1916User: exponent Language: Pascal Result: Accepted Time:996 ms Memory:6868 kb ****************************************************************/ type edge=recordv,w,n:longint; end; const maxm=150001; maxn=50001; maxk=11; var e:array[0..maxm] of edge; h:array[0..maxn] of longint; f:array[0..maxn,0..maxk] of int64; n,m,k,i,cnt,u,v,w:longint; procedure add(u,v,w:longint); begininc(cnt); e[cnt].v:=v; e[cnt].w:=w; e[cnt].n:=h[u]; h[u]:=cnt; end; function min(a,b:int64):int64; beginif a>b then exit(b); exit(a); end; function max(a,b:int64):int64; beginif a>b then exit(a); exit(b); end; function calc(a,u,r:longint):int64; var v,p:longint; tmp:int64; beginif f[u,r]>0 then exit(f[u,r]); p:=h[u]; tmp:=0; while p<>0 dobeginv:=e[p].v; if v<>a thentmp:=max(tmp,calc(u,v,r)+e[p].w); p:=e[p].n; end; if r>0 thenbeginp:=h[u]; while p<>0 dobeginv:=e[p].v; if v<>a thentmp:=min(tmp,calc(u,v,r-1)+e[p].w); p:=e[p].n; end; end; f[u,r]:=tmp; exit(tmp); end; beginreadln(n,m,k); for i:=1 to m dobeginreadln(u,v,w); add(u,v,w); end; writeln(calc(0,1,k)); end.

轉(zhuǎn)載于:https://www.cnblogs.com/exponent/archive/2011/08/24/2152325.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1916的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。