一个不错的题解 ： 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[..mm,..,..]of int64; f:array[..]of int64; map:array[..,..]of boolean; j,k,l,n,m,i,state,p,temp,top:longint; ans1,ans2:int64;begin readln(p); while p<> do begin dec(p); read(n,m); fillchar(f,sizeof(f),); for i:= to n do read(f[i]); if n= then begin writeln(f[],''); continue; end; readln; fillchar(map,sizeof(map),false); fillchar(way,sizeof(way),); fillchar(dp,sizeof(dp),); for i:= to m do begin read(j,k); map[j,k]:=true; map[k,j]:=true; end; top:=<<n-; ans1:=-; ans2:=; for i:= to top do for j:= to n do if (i and ( << (j-) )<>) then for k:= to n do if (j<>k) and ((i and ( << (k-) ))<>) and (map[j,k]) then begin if i=(<<(j-))+(<<(k-)) then begin dp[i,j,k]:=f[j]+f[k]+f[j]*f[k]; way[i,j,k]:=; end else begin for l:= to n do if (j<>l) and (l<>k) and (i and ( << (l-))<>)and map[k,l] then begin state:=i-(<<(j-)); if dp[state,k,l]=- 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=- then writeln('0 0') else writeln(ans1,' ',ans2 div ); end;end.
