算法

状压dp

题目描述

给出数个任务，每个任务有耗时和ddl，超过ddl的时间会扣除相应分数，要求找出得分最高的完成顺序。

解题思路

通过状态压缩，将完成的任务存在一个整形中（通过二进制压缩），转移方程为：
tmp = max(sum[lst] + a[x].day - a[x].ddl, 0);
f[s] = min(f[s], f[lst] + tmp);

代码

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int maxn = 30;
const int maxpd = 2000000;
struct At {
    string s;
    int ddl, day;
}   a[maxn];
int f[maxpd], sum[maxpd], pre[maxpd];
void dfs(int s) {
    if (s == 0)    return;
    dfs(s^(1<<(pre[s]-1)));
    cout << a[pre[s]].s << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        memset(a, 0, sizeof(a));
        int n;
        cin >> n;
        string s;
        int ddl, day;
        for (int i = 1; i <= n; i++) {
            cin >> s >> ddl >> day;//使用VS（C++）而不是dev（G++）
            a[i].s=s;
            a[i].ddl=ddl;
            a[i].day=day;
        }
        memset(f, 0x37, sizeof(f));
        memset(sum, 0, sizeof(sum));
        memset(pre, 0, sizeof(pre));
        f[0] = 0;
        for (int s = 1; s < (1 << n); s++) {
            for (int x = 1; x <= n; x++) {
                int xx = (1 << (x - 1));
                if (!(s&xx)) continue;
                int lst = s ^ xx;
                int tmp = max(sum[lst] + a[x].day - a[x].ddl, 0);
                if (f[lst] + tmp <= f[s]) {//同样值应后做大的
                    f[s] = f[lst] + tmp;
                    sum[s] = sum[lst] + a[x].day;
                    pre[s] = x;
                }
            }
        }
        cout << f[(1 << n) - 1] << endl;
        dfs((1 << n) - 1);
    }
    return 0;
}
/*
2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3
*/

题目总结

状压dp一般是由于过程中存在多种状态，此时通过二进制进行压缩