原文地址:http://www.cnblogs.com/Kenfly/archive/2011/03/30/2000364.html
题目: http://acm.hdu.edu.cn/showproblem.php?pid=1074
题意: 学生要完成各科作业, 给出各科老师给出交作业的期限和学生完成该科所需时间, 如果逾期一天则扣掉一单位学分, 要你求出完成所有作业而被扣最小的学分, 并将完成作业的顺序输出.
解题: 刚开始以为是背包, 但背包难以记录输出顺序, 所以只能换另一种DP方式, 这里科目最大数目才15, 只要有全枚举的思想来DP就可以解决了, 有一个专有名词叫状态压缩DP. 状态压缩DP采用二制进的思想,
1, 0分别代表有或否.
如:
3的二进制为 11, 则代表完成了每一,二个科目的状态, 101代表完成了第一三两个科目的状态.
这样, 可以从0->(1 << N)来获取所有状态, 并进行适当的状态转移. 对该题来说 D[s]代表集合s的状态, 要得到D[s]的状态, 可以从0 - N 分别检查是否在s集合内[s & (1 << i) > 0则表示i在集合s上,反之..], 如果i在s集合内,
刚D[s]可从D[s-{i}]来获得, [s-{i},可以s - (1<<i)来计算]. 这样表示在已完成了s-{i}的基础上再完成i后的装态, 遍历i, 取最优解.
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <stack> using namespace std; const int MAXN = 15 + 1; const int INF = 0x7fffffff; struct Homework { string name; int deadline; int time; }Data[MAXN]; struct DPT { int time; int score; int last; int pos; }DP[1 << MAXN]; int main() { int T, n; cin >> T; while(T--) { cin >> n; for(int i = 0; i < n; ++i) cin >> Data[i].name >> Data[i].deadline >> Data[i].time; int endState = 1 << n; int recent = 0; int reduce = 0; int past = 0; for(int s = 1; s < endState; ++s) { DP[s].score = INF; for(int i = n - 1; i >= 0; --i) { recent = 1 << i; if(s & recent) { past = s - recent; reduce = DP[past].time + Data[i].time - Data[i].deadline; if(reduce < 0) reduce = 0; if(reduce + DP[past].score < DP[s].score) { DP[s].score = reduce + DP[past].score; DP[s].pos= i; DP[s].last = past; DP[s].time = DP[past].time + Data[i].time; } } } } stack<int> path; recent = endState - 1; while(recent) { path.push(DP[recent].pos); recent = DP[recent].last; } cout << DP[endState - 1].score << endl; while(!path.empty()) { int top = path.top(); cout << Data[top].name << endl; path.pop(); } } return 0; }