前几天刚写了一道状压DP入门题,结果这次就遇到了,在比赛最后一点时间一眼看破,无奈只有想法,写不来……

不过赛后尝试写的时候遇到了一个自己不会的问题,也就是说假如比赛的时候开了这道题,我也会一直卡着。

题意:
给你很多个行李的位置和起点的位置,要你把所有行李搬运到起点,一次只能搬一个或者两个,花费是距离,求最小花费。行李最多24个。

思路
状压dp,对于每一个状态,我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的,那么,我通过从小到大枚举状态,在保证我当前状态最优的前提下,由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举,找到第一个它能够搬运的行李,每次都拓展这个状态即可。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int max_n = 30;
const int max_m = 1 << 24;

int n, tmp;
int dp[max_m], pre[max_m];

pii nodes[max_n];
int dis[max_n][max_n];

inline int calcul(int a, int b)
{
    return (nodes[a].first - nodes[b].first) * (nodes[a].first - nodes[b].first) + (nodes[a].second - nodes[b].second) * (nodes[a].second - nodes[b].second);
}

int main()
{
    scanf("%d %d %d", &nodes[29].first, &nodes[29].second, &n);
    nodes[n] = nodes[29];
    each(i, n) scanf("%d %d", &nodes[i].first, &nodes[i].second);
    each(i, n + 1) range(j, i + 1, n) dis[i][j] = dis[j][i] = calcul(i, j);
    fill(dp, 0x3f), dp[0] = 0;
    each(i, (1 << n)) if (dp[i] != inf) each(j, n) if (!(i & (1 << j)))
    {
        int t = (i | (1 << j));
        if (dp[t] > (tmp = dp[i] + 2 * dis[j][n])) {
            dp[t] = tmp;
            pre[t] = i;
        }
        each(k, n) if (!(t & (1 << k)))
        {
            int p = (t | (1 << k));
            if (dp[p] > (tmp = dp[i] + dis[k][n] + dis[j][n] + dis[k][j])) {
                dp[p] = tmp;
                pre[p] = i;
            }
        }
        break ;
    }
    int cur = (1 << n) - 1, ps, det;
    printf("%d\n0 ", dp[cur]);
    while (cur != 0) {
        ps = pre[cur];
        det = cur - ps;
        each(i, n) if (det & (1 << i)) printf("%d ", i + 1);
        printf("0 ");
        cur = ps;
    }
    return 0;
}
Categories: 状压DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

状压DP

BZOJ 4197 寿司晚宴

上一场多校一道状压DP的原题。 那我肯定是去做原题啦。 多校的时候我还 Read more…

状压DP

状压DP 再入门 !!!

昨天写状压DP被煞笔天海和死肥宅带鱼嘲笑了 Damn! 然而事实也是一 Read more…

状压DP

CodeForces 11D A Simple Task

今天做的不太一样的状压,从去年的专题找的,看到学长并没有写是已经写过了 Read more…