Problem
acm.hdu.edu.cn/showproblem.php?pid=1074
题意
n 份作业,分别给出名字、完成所需时间 cost、最迟上交时间 deadline。
作业每迟交一天扣一分。问最少的扣分数。
Analysis
状态压缩DP。
用集合 S 记录已经做完的作业。
dp[S]:已经做了 S 要扣的最少的分数
状态转移:dp[S] = min { dp[ S | 1 << i ] + score | i NOT IN S }
其中:score = max { 0 , time[S] + homework[i].cost - homework[i].deadline },即做完 S 后做 i 要多扣的分数;
time[S] = Zigma { homework[i].cost | i IN S },即做 S 所用的时间和。
因为要打印做作业的顺序,且是在最优情况下字典序最小的方案,所以用辅助的数组记录顺序。
记忆化搜索的过程是由大集合的答案推小集合,记录的是后继,即:nxt[S]:做完 S 后做哪个作业;
而递推版是由小集合推大集合,记录的是前驱,即:pre[S]:S 中最后做的作业。最后 借助栈逆序输出。
记忆化搜索找下一个作业的循环是从 0 到 n-1,而递推写法则要从 n-1 到 0(见代码注释)。这个跟那个字典序最小方案的要求有关。我觉得:因为数据输入是按字典序,搜索版是从大集合推小集合,从前往后遍历可以让字典序大的覆盖小的,出现在更大的集合里,所以就更晚出现;递推版就刚好相反。(这个理解不知道对不对)
Source code
记忆化搜索版
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 15, BIG = 123456789;
struct
{
string nm;
int c, d;
} hw[N];
int dp[1<<N], nxt[1<<N], n;
int dfs(int s, int t)
{
if(s == (1 << n) - 1)
return dp[s] = 0;
if(dp[s] >= 0)
return dp[s];
dp[s] = BIG;
for(int i=0, score; i<n; ++i) // 遍历顺序从小到大
if(s >> i & 1 ^ 1)
{
score = max(0, t + hw[i].c - hw[i].d);
score += dfs(s|1<<i, t+hw[i].c);
if(score < dp[s])
{
nxt[s] = i;
dp[s] = score;
}
}
return dp[s];
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--)
{
cin >> n;
for(int i=0; i<n; ++i)
cin >> hw[i].nm >> hw[i].d >> hw[i].c;
memset(dp, -1, sizeof dp);
memset(nxt, -1, sizeof nxt);
cout << dfs(0, 0) << '\n';
for(int i=0; ~nxt[i]; i|=1<<nxt[i])
cout << hw[nxt[i]].nm << '\n';
}
return 0;
}
递推版
#include <cstring>
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 15;
struct
{
string nm;
int c, d;
} hw[N];
int dp[1<<N], pre[1<<N], tm[1<<N];
stack<string> ans;
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
for(int i=0; i<n; ++i)
cin >> hw[i].nm >> hw[i].d >> hw[i].c;
memset(pre, -1, sizeof pre);
memset(dp, 5, sizeof dp);
dp[0] = tm[0] = 0;
for(int s=1, e=(1<<n); s<e; ++s)
for(int i=n-1, score; ~i; --i) // 遍历顺序从大到小
if(s >> i & 1)
{
score = dp[s^1<<i] + max(0, tm[s^1<<i]+hw[i].c-hw[i].d);
if(score < dp[s])
{
dp[s] = score;
pre[s] = i;
tm[s] = tm[s^1<<i] + hw[i].c;
}
}
cout << dp[(1<<n)-1] << '\n';
for(int i=(1<<n)-1; ~pre[i]; i^=1<<pre[i])
ans.push(hw[pre[i]].nm);
for( ; !ans.empty(); ans.pop())
cout << ans.top() << '\n';
}
return 0;
}