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;
}