war2 洛谷模拟赛day2 t3 状压

（new ）   war2

题解：总体数据而言，我们很容易想到着就是DP啊，我们DP数组,用状态压缩，代表有那些点已经被占领过了，代表上一次我占的是那个。对于每一次状态转移，若当前我们要占领的Portal在占领后有加分，那么就转移加分与基础值的和，否则只转移基础值。最后判断一下当代表的状态已经有占领个了，就记录下当前的最大值。

var

n,m,tot,cnt,ans,x,y,c:int64;

i,j,k:longint;

a:array[-100..100]of int64;

f,b:array[0..1<<18,0..20]of int64;// 2^18

function max(x,y:int64):int64;

 begin

  if x>y then exit(x) else exit(y);

 end;

begin

readln(n,m,k);

for i:=1 to n do read(a[i]);

readln;

for i:=1 to k do

begin

 readln(x,y,c);

 inc(b[x,y],c);

end;

for i:=1 to n do

 f[1<<(i-1)][i]:=a[i];

 tot:=(1<<n)-1;

  for k:=0 to tot do //every state

   begin

    cnt:=0;

    for i:=1 to n do

      begin

        if ((1<<(i-1)) and k)>0 then

          begin

            inc(cnt);

           //  if k=7 then writeln(i,' ',cnt);

            // writeln(cnt);

             for j:=1 to n do

              if (1<<(j-1))and k=0 then

               f[k or (1<<(j-1))][j]:=max(f[k or (1<<(j-1)) ][j],f[k,i]+b[i,j]+a[j]);// 1000-->1100,当前点占了所得到的值

          end;

      end;

    if cnt=m then

     begin

       for i:=1 to n do

         if k and (1<<(i-1))>0 then ans:=max(ans,f[k,i]);

         // writeln(cnt);

     end;

    end;

 writeln(ans);

 end.

war2 洛谷模拟赛day2 t3 状压的相关教程结束。