DIV2
250的题过以前难了一点点，submit的很顺利，500的题很长，看了半天，没看懂，再者，见到那字符串就没啥胃口了，看1000的题，想了想，有了思路，但不确定是否可以，那个时候还40来分钟吧，然后就悲剧了，写的很搓，手慢。到Challenge结束后，才写完并Debug完，看DIV2中过的人，也是那样类似哈密顿DP的方法过的。
大意：有张图，记顶点1...n,A,B，要让A尽可能经过1..n中的点，然后到达B，但从Xi到Xj的费用是map[i][j] * (1 + cnt()),cnt()表示之前已经经过1..n中的点的数目，然后从这个过程有一个时间限制T。
然后就先建图，这里把我的精神写搓掉了，然后DP[i][j]，i表示状态,j表示最后停在j点处的时间，要让这个尽可能小，最后就是DP[i][j]，然后枚举状态i，找出到达B处的，时间在要求内，并且点数最多即可。
这些都是基于点数较少，可能枚举出所有的情况，这样想，跟哈密顿DP法就如出一辙了。
注意longlong以及dp[i][j]==-1的要continue掉，路径的费用要算对。
1 #include < iostream > 2 #include < string > 3 #include < algorithm > 4 #include < string .h > 5 #include < vector > 6 #include < math.h > 7 #include < time.h > 8 #include < queue > 9 #include < set > 10 using namespace std; 11 12 const long long MAX = 55 ; 13 const long long INF = 1000000001 ; 14 15 struct NODE 16 { 17 long long x, y; 18 long long t; 19 NODE() {} 20 NODE( long long xx, long long yy, long long tt) : x(xx), y(yy), t(tt) {} 21 }; 22 23 long long map[MAX][MAX]; // distance 24 long long vetex[MAX][MAX]; // flag 25 long long nodeCnt; 26 long long n; 27 long long citySizeX; 28 long long citySizeY; 29 long long move[ 4 ][ 2 ] = { - 1 , 0 , 0 , 1 , 1 , 0 , 0 , - 1 }; 30 long long path[ 1 << 16 ][ 20 ]; 31 32 long long dp[ 1 << 16 ][ 20 ]; 33 34 bool check( long long x, long long y) 35 { 36 if (x < 0 || y < 0 || x >= citySizeX || y >= citySizeY) return false ; 37 if (vetex[x][y] == - 1 ) return false ; 38 return true ; 39 } 40 41 long long oneCnt( long long x) 42 { 43 long long res = 0 ; 44 while (x) 45 { 46 if (x & 1 ) res ++ ; 47 x >>= 1 ; 48 } 49 return res; 50 } 51 52 void bfs( long long x, long long y, long long ss) 53 { 54 vector < NODE > q; 55 long long s[MAX][MAX]; 56 memset(s, 0 , sizeof (s)); 57 s[x][y] = 1 ; 58 q.push_back(NODE(x, y, 0 )); 59 for ( long long i = 0 ; i < q.size(); i ++ ) 60 { 61 for ( long long j = 0 ; j < 4 ; j ++ ) 62 { 63 long long xx = q[i].x + move[j][ 0 ]; 64 long long yy = q[i].y + move[j][ 1 ]; 65 if (check(xx, yy) && s[xx][yy] == 0 ) 66 { 67 s[xx][yy] = 1 ; 68 if (vetex[xx][yy] > 0 ) map[ss][vetex[xx][yy]] = q[i].t + 1 ; 69 q.push_back(NODE(xx, yy, q[i].t + 1 )); 70 } 71 } 72 } 73 } 74 75 void show( long long i) 76 { 77 while (i) 78 { 79 printf( " %d " , i & 1 ); 80 i >>= 1 ; 81 } 82 printf( " \n " ); 83 } 84 85 void dfs( long long i, long long j) 86 { 87 while ( 1 ) 88 { 89 printf( " #%d\n " , j + 1 ); 90 if (path[i][j] == - 1 ) break ; 91 long long t = path[i][j]; 92 i = t / 100 ; 93 j = t % 100 ; 94 95 } 96 97 for (i = 1 ; i <= nodeCnt; i ++ ) 98 { 99 for ( long long j = 1 ; j <= nodeCnt; j ++ ) 100 { 101 printf( " %d " , map[i][j]); 102 } 103 printf( " \n " ); 104 } 105 } 106 107 long long go(vector < string > city, long long T) 108 { 109 nodeCnt = 0 ; 110 citySizeX = city.size(); 111 citySizeY = city[ 0 ].size(); 112 long long i, j; 113 long long ki, kj, qi, qj; 114 for ( long long i = 0 ; i < city.size(); i ++ ) 115 { 116 for ( long long j = 0 ; j < city[i].size(); j ++ ) 117 { 118 if (city[i][j] == ' . ' ) vetex[i][j] = 0 ; 119 else if (city[i][j] == ' # ' ) vetex[i][j] = - 1 ; 120 else if (city[i][j] == ' K ' ) 121 { 122 ki = i, kj = j; 123 } 124 else if (city[i][j] == ' Q ' ) qi = i, qj = j; 125 else if (city[i][j] == ' G ' ) vetex[i][j] = ++ nodeCnt; 126 } 127 } 128 vetex[ki][kj] = ++ nodeCnt; 129 vetex[qi][qj] = ++ nodeCnt; 130 n = nodeCnt - 2 ; 131 132 // get distance 133 for ( long long i = 1 ; i <= nodeCnt; i ++ ) 134 { 135 for ( long long j = 1 ; j <= nodeCnt; j ++ ) 136 { 137 if (i == j) map[i][j] = 0 ; 138 else map[i][j] = INF; 139 } 140 } 141 for ( long long i = 0 ; i < city.size(); i ++ ) 142 { 143 for ( long long j = 0 ; j < city[i].size(); j ++ ) 144 { 145 if (vetex[i][j] > 0 ) bfs(i, j, vetex[i][j]); 146 } 147 } 148 149 memset(dp, - 1 , sizeof (dp)); 150 memset(path, - 1 , sizeof (path)); 151 for ( long long i = 0 ; i < n; i ++ ) 152 { 153 dp[ 1 << i][i] = map[n + 1 ][i + 1 ]; 154 } 155 for ( long long i = 0 ; i < ( 1 << n); i ++ ) 156 { 157 for ( long long j = 0 ; j < n; j ++ ) 158 { 159 if (( 1 << j) & i) 160 { 161 if (dp[i][j] == - 1 ) continue ; 162 for ( long long kk = 0 ; kk < n; kk ++ ) 163 { 164 if (kk == j) continue ; 165 if (( 1 << kk) & i) continue ; 166 if (map[j + 1 ][kk + 1 ] == INF) continue ; 167 long long num = oneCnt(i); 168 if (dp[i + ( 1 << kk)][kk] == - 1 || dp[i][j] + map[j + 1 ][kk + 1 ] * ( 1 + num) < dp[i + ( 1 << kk)][kk]) 169 { 170 dp[i + ( 1 << kk)][kk] = dp[i][j] + map[j + 1 ][kk + 1 ] * ( 1 + num); 171 path[i + ( 1 << kk)][kk] = i * 100 + j; 172 } 173 } 174 } 175 } 176 } 177 178 long long ans = 0 ; 179 for ( long long i = 0 ; i < ( 1 << n); i ++ ) 180 { 181 for ( long long j = 0 ; j < n; j ++ ) 182 { 183 if (( 1 << j) & i) 184 { 185 if (dp[i][j] == - 1 ) continue ; 186 if (dp[i][j] + map[j + 1 ][n + 2 ] * ( 1 + oneCnt(i)) <= T) 187 { 188 if (oneCnt(i) > ans) 189 { 190 ans = oneCnt(i); 191 if (ans == 4 ) 192 { 193 show(i); 194 dfs(i, j); 195 } 196 } 197 } 198 } 199 } 200 } 201 return ans; 202 } 203 204 class Gifts 205 { 206 public : 207 int maxGifts(vector < string > city, int T) 208 { 209 return go(city, T); 210 } 211 };
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/20/1716545.html
