cdoj 1134 男神的约会状压dp-白红宇

cdoj 1134 男神的约会状压dp

阅读量：5293 次

发布时间：2019-06-14

本文共 1148 字，大约阅读时间需要 3 分钟。

给一个10*10的方格，每个格子里面有0-9，走到一个格子，就要在这个格子待一段时间，时间长度为这个格子的数字。从左上角走到右下角，要求0-9必须每种格子都要走到，输出最短时间。

在平常dp的基础上多开一维，然后用二进制代表哪些走到过哪些没有走到过，最后输出dp[10][10][1023]就可以。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
            8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 using namespace std;14 #define pb(x) push_back(x)15 #define ll long long16 #define mk(x, y) make_pair(x, y)17 #define lson l, m, rt<<118 #define mem(a) memset(a, 0, sizeof(a))19 #define rson m+1, r, rt<<1|120 #define mem1(a) memset(a, -1, sizeof(a))21 #define mem2(a) memset(a, 0x3f, sizeof(a))22 #define rep(i, n, a) for(int i = a; i
                 
                   pll;26 const double PI = acos(-1.0);27 const double eps = 1e-8;28 const int mod = 1e9+7;29 const int inf = 1061109567;30 const int dir[][2] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1} };31 int dp[10][10][1<<10], a[10][10];32 int main()33 {34 for(int i = 0; i<10; i++)35 for(int j = 0; j<10; j++)36 scanf("%d", &a[i][j]);37 mem2(dp);38 dp[0][0][1<