首页 > 代码库 > 【以前的空间】poj 2288 Islands and Bridges
【以前的空间】poj 2288 Islands and Bridges
一个不错的题解 : http://blog.csdn.net/accry/article/details/6607703
这是一道状态压缩。每个点有一个值,我们最后要求一个最值sum。sum由三部分组成:①每个点的值②每个点与他相邻的点的乘积③如果存在三个点成环,还要加上这三个点的值的乘积。
状态转移方程为:dp[i][j][k]=max(dp[i,j,k],dp[i‘][k][l]+temp) j表示当前点,k表示上一个点,l表示上上一个点。
其中i,i‘表示可以走到i点的状态,temp表示这个状态过来需要加的值,它等于value[j]+value[j]*value[k](如果j,k,l成环还要+value[j]*value[k]*value[l]).
当i状态表示只由两个点构成时,dp[i][j][k]=value[j]+value[j]*value[k].
但是此题不止要求最大值,还有求最大值的个数。于是我们开一个way数组,way[i][j][k]表示i状态由当前点i和上一个点k所有个方案数。于是如果dp[i][j][k]=dp[i‘][k][l]+temp是way[i][j][k]+=way[i‘][k][l],如果是dp[i][j][k]<dp[i‘][k][l]+temp时way[i][j][k]=way[i‘][k][l].
本来是这样,但是我很蛋疼得想如果在dp的同时去更新最大值和最大个数。于是就导致1个小时不断的wa,不断找反例,不断改,终于过了orz……。
如果要按我那么做,就是不断更新最大值,那么就一定要在第二个循环内……以及一些奇奇怪怪的限制,只能说这是一个神奇的经历,不断读程序理解思想……(其实是因为没有数据)说明我以前太依赖现有数据去调程序了……
var dp,way:array[0..mm,1..14,1..14]of int64; f:array[0..14]of int64; map:array[0..14,0..14]of boolean; j,k,l,n,m,i,state,p,temp,top:longint; ans1,ans2:int64; begin readln(p); while p<>0 do begin dec(p); read(n,m); fillchar(f,sizeof(f),0); for i:=1 to n do read(f[i]); if n=1 then begin writeln(f[1],‘ 1‘); continue; end; readln; fillchar(map,sizeof(map),false); fillchar(way,sizeof(way),0); fillchar(dp,sizeof(dp),255); for i:=1 to m do begin read(j,k); map[j,k]:=true; map[k,j]:=true; end; top:=1<<n-1; ans1:=-1; ans2:=0; for i:=0 to top do for j:=1 to n do if (i and ( 1<< (j-1) )<>0) then for k:=1 to n do if (j<>k) and ((i and ( 1<< (k-1) ))<>0) and (map[j,k]) then begin if i=(1<<(j-1))+(1<<(k-1)) then begin dp[i,j,k]:=f[j]+f[k]+f[j]*f[k]; way[i,j,k]:=1; end else begin for l:=1 to n do if (j<>l) and (l<>k) and (i and ( 1<< (l-1))<>0)and map[k,l] then begin state:=i-(1<<(j-1)); if dp[state,k,l]=-1 then continue; temp:=f[j]*f[k]+f[j]+dp[state,k,l]; if map[j,l] then inc(temp,f[j]*f[k]*f[l]); if dp[i,j,k]>temp then continue; if dp[i,j,k]=temp then inc(way[i,j,k],way[state,k,l]); if dp[i,j,k]<temp then begin dp[i,j,k]:=temp; way[i,j,k]:=way[state,k,l]; end; end; end; if (i=top) then begin if ans1=dp[i,j,k] then ans2:=ans2+way[i,j,k] else if ans1<dp[i,j,k] then begin ans1:=dp[i,j,k]; ans2:=way[i,j,k]; end; end; end; if ans1=-1 then writeln(‘0 0‘) else writeln(ans1,‘ ‘,ans2 div 2); end; end.
【以前的空间】poj 2288 Islands and Bridges