HDU 1074 Doing Homework(经典状压dp)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 16;
struct Node {
    char name[110];
    int D,C;
} node[maxn];
int dp[1<<maxn], pre[1<<maxn];
int n;

void print_ans(int now) {
    if (!now) return;
    int temp;
    for (int i = 0; i < n; i++) {
        if ((now & (1<<i)) && !(pre[now] & (1<<i))) {
            temp = i;
            break;
        }
    }
    print_ans(pre[now]);
    puts(node[temp].name);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(dp, 0x3f, sizeof(dp));
        memset(pre, 0, sizeof(pre));
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%s%d%d", node[i].name, &node[i].D, &node[i].C);
        dp[0] = 0;
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) continue;
                int s = 0;
                for (int k = 0; k < n; k++)
                    if (i & (1 << k)) s += node[k].C;
                s += node[j].C;
                if (s > node[j].D) s -= node[j].D;
                else s = 0;
                if (dp[i|(1<<j)] > dp[i] + s) {
                    dp[i|(1<<j)] = dp[i] + s;
                    pre[i|(1<<j)] = i;
                }
            }
        }
        printf("%d\n", dp[(1<<n)-1]);
        print_ans((1<<n)-1);
    }
}