VJP1456 最小总代价（状压）

链接

这题卡了一天  刚开始没考虑第一个传的和最后一个传的 感觉挺简单 啪啪的敲完 居然还过了17组数据。。

正解：dp数组一维保存状态 一维保存当前传到了谁 再枚举是由谁传过来的 这样可以保证正确性

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define INF 0xfffffff

 #define M 100010

 int dp[M][],a[][],q[][M],f[M];

 int main()

 {

     int i,j,k,n;

     while(scanf("%d",&n)!=EOF)

     {

         memset(f,,sizeof(f));

         for(i = ; i <= n ; i++)

             for(j = ; j <= n ;j++)

             scanf("%d",&a[i][j]);

         int ans = INF;

         for(i =  ; i <= n ;i++)

             for(j =  ; j <= <<n ;j++)

             dp[j][i] = INF;

         for(i =  ; i < n ; i++)

         {

             q[][i+] = <<i;

             dp[<<i][i+] = ;

         }

         k = n;

         for(i = ; i <= n ;i++)

         {

             int tt = ;

             for(j =  ; j <= k ; j++)

             {

                 for(int e =  ; e < n ; e++)

                 {

                     for(int o =  ; o < n ; o++)

                     {

                         if(((~q[(i-)%][j])&(<<o))==)

                         continue;

                         if(o!=e)

                         {

                             dp[q[(i-)%][j]+(<<o)][o+] = min(dp[q[(i-)%][j]+(<<o)][o+],dp[q[(i-)%][j]][e+]+a[e+][o+]);

                         }

                         if(!f[q[(i-)%][j]+(<<o)])

                         {

                             tt++;

                             q[i%][tt] = q[(i-)%][j]+(<<o);

                             f[q[(i-)%][j]+(<<o)] = ;

                         }

                     }

                 }

             }

             k = tt;

         }

         for(i = ; i <= n ; i++)

         ans = min(ans,dp[(<<n)-][i]);

         printf("%d\n",ans);

     }

     return ;

 }