2009年11月02日 16:25 阅读(38) 评论(1) 分类：program 《vijos p1456 最小总代价》

我承认我蛋疼把写在vijos的题解在这里又贴一遍
我觉得这个用宽搜生成状态然后dp的写法很诡异
相当诡异

编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
├ 测试数据 11：答案正确... 0ms
├ 测试数据 12：答案正确... 0ms
├ 测试数据 13：答案正确... 0ms
├ 测试数据 14：答案正确... 0ms
├ 测试数据 15：答案正确... 9ms
├ 测试数据 16：答案正确... 9ms
├ 测试数据 17：答案正确... 0ms
├ 测试数据 18：答案正确... 9ms
├ 测试数据 19：答案正确... 25ms
├ 测试数据 20：答案正确... 0ms
-------------------------
Accepted 有效得分：100 有效耗时：52ms
Vijos Easy
一次AC很爽
我承认我写得很诡异
用f[i,j]表示状态为i，当前在第j点所能得到的最小值
i是用2进制表示的状态
初始化f[1 shl(i-1),i]=0
然后把所有的1 shl(i-1)存到一个队列里
就是记录当前已经扩展的状态
之后每次从队头拿一个状态出来
枚举i，j
其中i表示队头状态当前所到达的点
j表示从i出发走到的下一个点
i要走过，j不能走过（这个用位运算判断）
然后去更新状态
把新生成的状态加入到队尾
一直做到队列里面剩一个状态
也就是那个最后全部都走过的状态

最后输出f[1 shl n-1,i]的最大值
下面是主过程
   fillchar(f,sizeof(f),$7f);//初始化
   fillchar(h,sizeof(h),0);//记录当前状态是否出现过的数组
   for i:=1 to n do
     begin
      s[i]:=1 shl(i-1);
      f[s[i],i]:=0;
      h[s[i]]:=true;
     end;
   p:=1;q:=n;//初始队头队尾
   while p
     begin
      for i:=1 to n do
       if (s[p] shr (i-1))and 1=1 then  //枚举并判断i是否合法
         for j:=1 to n do
          if (s[p] shr (j-1))and 1=0 then //枚举并判断j是否合法
            begin
             x:=s[p] xor (1 shl (j-1));  //生成新状态
             if f[x,j]>f[s[p],i]+a[i,j] then f[x,j]:=f[s[p],i]+a[i,j];  //更新f数组
             if not h[x] then //判断新状态是否出现过，没出现过就加入队尾
               begin
                h[x]:=true;
                inc(q);
                s[q]:=x;
               end;
            end;
      inc(p);
     end;