题目大意：

有n($\le 15$)个作业，每个作业有个name, deadline（截止日期），cost（做作业花的时间），如果没有按时完成某个作业，惩罚分数为超出的时间，求一个合理的顺序使得惩罚分数最小，如果有多个方案分数相同，输出字典序最小的。

题目分析

看到$n \le 15$可知状压dp：dp[S]表示完成S状态的最小惩罚分数，转移也较为简单：$$dp[i | (1 << (j - 1))] = min(dp[S | (1 << (j - 1))], dp[i] + getTime(i) + cost[j] - deadline[j])$$。因为要输出方案，于是记录一个from数组表示这个状态是从哪个状态转移来的。又因为要求字典序最小，现将name排序，这样在转移时如果$dp[i | (1 << (j - 1))] == dp[i] + getTime(i) + cost[j] - deadline[j])$，并且$i | (1 << (j - 1)) < from[i]$，那么$from[i] = i | (1 << (j - 1))$，来保证字典序最小。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 20, S = 33000, OO = 0x3f3f3f3f;

int n, dp[S], T, from[S];

vector<int> ans;

struct node{

    string name;

    int dl, cost;

    inline bool operator < (const node &b) const {

        return name < b.name;

    }

}task[N];

inline int getTime(int s){

    int ans = 0;

    for (int i=0; (1<<i)<=s; i++)

        if ((1<<i)&s)

            ans += task[i + 1].cost;

    return ans;

}

inline void init(){

    memset(dp, OO, sizeof dp), dp[0] = 0;

    memset(from, 0, sizeof from);

    ans.clear();

}

inline int find(int x){

    int l = 1, r = 15;

    while (l<=r) {

        int mid = (l + r) >> 1;

        if (1<<(mid-1) == x) return mid;

        else if (1<<(mid-1) > x) r = mid - 1;

        else l = mid + 1;

    }

    return 0;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL), cout.tie(NULL);

    cin >> T;

    while(T--){

        init();

        cin >> n;

        for (int i=1; i<=n; i++) cin >> task[i].name >> task[i].dl >> task[i].cost;

        sort(task + 1, task + n + 1);

        for (int i=0; i<(1<<n); i++) {

            for(int j=1; j<=n; j++) {

                if (i&(1<<(j-1))) continue;

                if (dp[i|(1<<(j-1))] > dp[i] + max(0, getTime(i) + task[j].cost - task[j].dl)) {

                    from[i|(1<<(j-1))] = i;

                    dp[i|(1<<(j-1))] = dp[i] + max(0, getTime(i) + task[j].cost - task[j].dl);

                }

                else if(dp[i|(1<<(j-1))] == dp[i] + max(0, getTime(i) + task[j].cost - task[j].dl)) {

                    if(i < from[i|(1<<(j-1))]) from[i|(1<<(j-1))] = i;

                }

            }

        }

        cout << dp[(1<<n)-1] << endl;

        int now = (1<<n)-1;

        while(now) {

            int diff = now ^ (from[now]);

            int pos = find(diff);

            // cout << now << " " << from[now] << " " << diff << " " << pos << endl;

            ans.push_back(pos);

            now = from[now];

        }

        for(int i=ans.size()-1; i>=0; i--) cout << task[ans[i]].name << endl;

    }

    return 0;

}

巴特西

HDU1074 Doing Home Work - 状压dp

题目大意：

题目分析

code

最新文章

热门文章