算法

狀壓dp

題目描述

給出數(shù)個(gè)任務(wù)，每個(gè)任務(wù)有耗時(shí)和ddl，超過ddl的時(shí)間會(huì)扣除相應(yīng)分?jǐn)?shù)，要求找出得分最高的完成順序。

解題思路

通過狀態(tài)壓縮，將完成的任務(wù)存在一個(gè)整形中（通過二進(jìn)制壓縮），轉(zhuǎn)移方程為：
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]) {//同樣值應(yīng)后做大的
                    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
*/

題目總結(jié)

狀壓dp一般是由于過程中存在多種狀態(tài)，此時(shí)通過二進(jìn)制進(jìn)行壓縮