HDU 4281 Judges' response（状压DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4281

题意：一场比赛要有若干个裁判去回答N个问题，第i个问题在(xi, yi)处，裁判解答该问题需要ci分钟，每个裁判最多能解答M分钟的问题，每个点只能被一个裁判访问，从一点走到另一点的时间为其欧几里得距离值，问：

1.最少需要多少裁判才能回答完所有问题

2.假设有无数个裁判，求回答完所有问题的最少行走时间（题目未说清，裁判最终要回到起点）

思路：可以先预处理出任意状态是否能够满足总解答时间 <= M

对于问题1：可以将权值和 <= M的集合看作一个个背包，dp[s]可以表示达到s状态所需的最小花费，对于没有交集的两个集合则有转移：dp[s | t] = min(dp[s | t], dp[t] + 1)

对于问题2：可以预处理出一个裁判遍历各个状态并回到起点所需的花费，然后对于任一状态，通过枚举子集找到其子集和子集补集的花费，因为裁判最后要回到起点故有转移：dp[s] = min(dp[s], dp[sub | 1] + dp[(s ^ sub) | 1])

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <climits>
#include <functional>
#include <deque>
#include <ctime>

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

const int inf = 0x3f3f3f3f;

struct node
{
    int x, y;
} p[20];

int n, m;
int dp[1 << 17][17], ans1[1 << 17], ans2[1 << 17], ok[1 << 17];
int dis[17][17], v[17];

int dist(int a, int b)
{
    return ceil(sqrt((p[a]. x - p[b].x) * (p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y)));
}

bool check(int s)
{
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        if (s & (1 << i))
            res += v[i];
    }
    if (res <= m) return true;
    return false;
}

void init()
{
    for (int i = 0; i < n; i++)
        scanf("%d%d", &p[i].x, &p[i].y);

    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = dist(i, j);

    for (int i = 0; i < (1 << n); i++)
        if (check(i))
            ok[i] = 1;
        else
            ok[i] = 0;
}

int solve1()
{
    memset(ans1, -1, sizeof(ans1));
    ans1[0] = 0;

    for (int s = 0; s < (1 << n); s++)
    {
        if (ok[s])
        {
            for (int t = 0; t < (1 << n); t++)
            {
                if (s & t == 1) continue;
                if (ans1[t] == -1) continue;

                // printf("%d %d %d\n", s, t, s | t);
                if (ans1[s | t] == -1)
                    ans1[s | t] = ans1[t] + 1;
                else
                    ans1[s | t] = min(ans1[s | t], ans1[t] + 1);
            }
        }
    }
    return ans1[(1 << n) - 1];
}

int solve2()
{
    memset(dp, -1, sizeof(dp));
    memset(ans2, -1, sizeof(ans2));

    dp[1][0] = 0;
    for (int s = 0; s < (1 << n); s++)
    {
        if (ok[s])
        {
            for (int i = 0; i < n; i++)
            {
                if (s & (1 << i) == 0) continue;
                if (dp[s][i] == -1) continue;

                for (int j = 0; j < n; j++)
                {
                    if (s & (1 << j) == 1) continue;
                    int t = s | (1 << j);

                    //printf("%d %d\n", s, t);
                    if (ok[t])
                    {
                        if (dp[t][j] == -1)
                            dp[t][j] = dp[s][i] + dis[i][j];
                        else
                            dp[t][j] = min(dp[t][j], dp[s][i] + dis[i][j]);
                    }
                }
            }
        }
    }

    for (int s = 0; s < (1 << n); s++)
        for (int i = 0; i < n; i++)
        {
            if (dp[s][i] == -1) continue;
            if (s & (1 << i) == 0) continue;

            if (ans2[s] == -1)
                ans2[s] = dp[s][i] + dis[i][0];
            else
                ans2[s] = min(ans2[s], dp[s][i] + dis[i][0]);
        }

    for (int s = 0; s < (1 << n); s++)
    {
        int sub = s;
        do
        {
            if (ans2[sub | 1] == -1 || ans2[(s ^ sub) | 1] == -1)
            {
                sub = (sub - 1) & s;
                continue;
            }

            if (ans2[s] == -1)
                ans2[s] = ans2[sub | 1] + ans2[(s ^ sub) | 1];
            else
                ans2[s] = min(ans2[s], ans2[sub | 1] + ans2[(s ^ sub) | 1]);

            sub = (sub - 1) & s;
        } while (sub != s);
    }
    return ans2[(1 << n) - 1];
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        init();
        int res1 = solve1(), res2 = solve2();
        printf("%d %d\n", res1, res2);
    }
    return 0;
}