首页 > 代码库 > HDU 3920Clear All of Them I（状压DP）

HDU 3920Clear All of Them I（状压DP）

2024-07-15 13:04:58   223人阅读

HDU 3920   Clear All of Them I

题目是说有2n个敌人，现在可以发n枚炮弹，每枚炮弹可以（可以且仅可以）打两个敌人，每一枚炮弹的花费等于它所行进的距离，现在要消灭所有的敌人，问最少花费是多少（反正题意大概就是这样啦，知道怎么回事就好了，解释不清了）

一看到n<=10而且又是在DP专题里的，就知道这个显然是状压DP，由于有2n个敌人，所以状态表示由当前状态再打两个人来转移，

10000100表示打了这两个敌人的最小花费

所以状态的转移是由前往后递推的，假如当前状态是cur，上一个状态是last，应该满足存在i！=j有last&(1<<i)=0且last&(1<<j)=0且last | (1<<i)|(1<<j) = cur，由此来更新当前的状态cur，最后的答案就是DP[(1<<(2n)) - 1]

注意到上面我们是要枚举i和j的，所以这个的总复杂度就是20 * 20 * 2^20，这显然是会超时的， 所以需要优化

注意到如果存在两队人(a,b)(c,d)我们先打(a, b)再打(c, d)和先打（c,d）在打(a, b)是一样的，所以我们完全可以每次取last中最小的一位是0的与后面所有的0组合，这样不仅没有漏掉解，而且复杂度也将到了O(20 * 2^20)这就可以过了

下面从前往后美剧上一个状态时递推时我是用的队列存的所有状态，其实枚举过去也是可以的

  1 //#pragma comment(linker,"/STACK:102400000,102400000")  2 #include <map>  3 #include <set>  4 #include <stack>  5 #include <queue>  6 #include <cmath>  7 #include <ctime>  8 #include <vector>  9 #include <cstdio> 10 #include <cctype> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 #define INF 1e9 17 #define inf (-((LL)1<<40)) 18 #define lson k<<1, L, mid 19 #define rson k<<1|1, mid+1, R 20 #define mem0(a) memset(a,0,sizeof(a)) 21 #define mem1(a) memset(a,-1,sizeof(a)) 22 #define mem(a, b) memset(a, b, sizeof(a)) 23 #define FOPENIN(IN) freopen(IN, "r", stdin) 24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 25 template<class T> T CMP_MIN(T a, T b) { return a < b; } 26 template<class T> T CMP_MAX(T a, T b) { return a > b; } 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; } 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; } 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; } 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    } 31  32 //typedef __int64 LL; 33 //typedef long long LL; 34 const int MAXN = 105; 35 const int MAXM = 100005; 36 const double eps = 1e-13; 37 //const LL MOD = 1000000007; 38  39 int T, N; 40 typedef double Point[2]; 41 Point st, p[MAXN]; 42 double dis[MAXN][MAXN], d[MAXN], dp[1<<21]; 43  44 double calc(Point a, Point b) 45 { 46     double x = a[0] - b[0]; 47     double y = a[1] - b[1]; 48     return sqrt(x*x + y*y); 49 } 50  51 void getDis() 52 { 53     for(int i=0;i<N;i++) 54     { 55         d[i] = calc(st, p[i]); 56         for(int j=i+1;j<N;j++) 57         { 58             dis[j][i] = dis[i][j] = calc(p[i], p[j]); 59         } 60     } 61 } 62  63 int main() 64 { 65     int t = 0; 66     scanf("%d", &T); 67     while(T--) 68     { 69         scanf("%lf %lf", &st[0], &st[1]); 70         scanf("%d", &N); 71         N <<= 1; 72         for(int i=0;i<N;i++) 73             scanf("%lf %lf", &p[i][0], &p[i][1]); 74         getDis(); 75         dp[0] = 0; 76         for(int i=1;i<(1<<N);i++) dp[i] = INF; 77         queue<int>q; 78         q.push(0); 79         while(!q.empty()) 80         { 81             int now = q.front(); q.pop(); 82             int f=0, r; 83             while( now & (1<<f)  && f < N) 84                 f++; 85             for(r = f + 1; r < N; r ++ ) 86                 if(!(now & (1<<r))) 87             { 88                 int next = now | (1<<f) | (1<<r); 89                 double minDis = MIN(d[f], d[r]) + dis[f][r]; 90                 if( fabs(dp[next] - INF) < eps ) 91                 { 92                     q.push(next); 93                     dp[next] = dp[now] + minDis; 94                 } 95                 else if( dp[now] + minDis < dp[next] ) 96                     dp[next] = dp[now] + minDis; 97             } 98         } 99         printf("Case #%d: %.2lf%\n", ++t, dp[(1<<N)-1]);100     }101     return 0;102 }

 


联系
我们