HDU 1074 Doing Homework

虽然可以算得上是道水题，但作为我第一道状压DP，还是把它写入我的博客。
觉得这道题作为入门题是极好的，比网上说的什么矩阵的好理解的多！！
因为几乎只涉及了状压

特别想感慨一句，dp真的是个优美的暴力啊……

题意：
有几门课的作业，分别给出截止时间，完成所需时间，没拖一天扣一分，问最少扣多少分，并输出写作业顺序。

思路：
总的思路是对于每一个状态，都进行课程的枚举，并计算花费时间，拖作业时间，从而进行状态转移，每次状态转移都使拖作业的时间最小即可。
不是暴力？？但是真的很优美！
课程数很小，只有15门，因此状压无压力。

AC Code

#include <cstdio>
#include <cstring>
#include <numeric>
#include <queue>
#include <stack>

using namespace std;

#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))

const int max_n = 16;
const int max_m = 110;

int n;
bool vis[1<<max_n];

struct co {
    int deadline, cost;
    char name[max_m];
} course[max_n];

struct p {
    int cost, bey, pre;
} dp[1 << max_n];

void output(int state)
{
    if (!state)
        return;
    output(dp[state].pre);
    int idx = state ^ dp[state].pre, pos = 0;
    while ((idx & 1) == 0)
        idx >>= 1, pos++;
    puts(course[pos].name);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        fill(vis, false);
        each(i, n) scanf("%s %d %d", course[i].name, &course[i].deadline, &course[i].cost);
        int en = (1 << n);
        each(i, en) each(j, n)
        {
            int j2 = (1 << j);
            if (!(i & j2)) {
                int cur = i | j2;
                dp[cur].cost = dp[i].cost + course[j].cost;
                int bey = (dp[cur].cost > course[j].deadline ? dp[cur].cost - course[j].deadline : 0) + dp[i].bey;
                if (!vis[cur] || bey < dp[cur].bey)
                    vis[cur] = true, dp[cur].bey = bey, dp[cur].pre = i;
            }
        }
        printf("%d\n", dp[en - 1].bey);
        output(en - 1);
    }
    return 0;
}