虽然可以算得上是道水题,但作为我第一道状压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;
}
Categories: 状压DP

发表评论

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

Related Posts

状压DP

BZOJ 4197 寿司晚宴

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

状压DP

状压DP 再入门 !!!

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

状压DP

CodeForces 11D A Simple Task

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