HDU1074 Doing Homework

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1074

题意

有n本作业,每本都有一个完成时间和提交截止时间,当完成作业后提交,每超过截止时间1分就扣1分,问怎么最小化扣的分数。

思路

由于n只有15,所以就可以用状压dp。 定义状态为$1~(1<<n)-1$,我们先枚举每个状态$i$,在枚举该状态的上一个状态,那怎么枚举呢?先枚举$0 ~ n-1$每个科目$j$,在判断下$i\&(1<<j)$是否为$1$,如果是,说明该状态的上一个状态为$i-(1<<j)$,再根据上一个状态来更新该状态。

1、判断上一个状态的扣分+j科目扣的分是否小于该状态的扣分。 2、满足1的情况下,更新该状态所需的时间,扣分,科目和该状态的父亲,因为最后还要输出路径。

所以需要定义一个结构体如下所示:

1
2
3
4
5
6
struct homework {
int id; // 记录科目
int time; // 记录所需时间
int cost; // 记录扣分
int fa; // 记录父亲,也就是上一个状态
}dp[1 << 15];

Code(15MS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll P = 1e9 + 7;
// const double eps = 1e-6;
// const double pi = acos(-1);

struct homework {
char name[105];
int d, c;
}a[20];

struct zy {
int fa, cost, time;
int id;
}dp[1 << 16];

void solve() {
int T;
cin >> T;
while(T--) {
mem(dp, 0);
int n;
cin >> n;
for(int i = 0;i < n; i++) {
cin >> a[i].name >> a[i].d >> a[i].c;
}

for(int i = 1;i < (1 << n); i++) {
dp[i].cost = INF;
for(int j = n - 1;j >= 0; j--) {
int temp = 1 << j;
if(temp & i) {
int tmp = i - temp;
int t = dp[tmp].time + a[j].c - a[j].d;
if(t < 0)
t = 0;
if(t + dp[tmp].cost < dp[i].cost) {
dp[i].cost = dp[tmp].cost + t;
dp[i].fa = tmp;
dp[i].id = j;
dp[i].time = dp[tmp].time + a[j].c;
}
}
}
}

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

stack<int> s;

int t = (1 << n) - 1;
while(dp[t].time) {
s.push(dp[t].id);
t = dp[t].fa;
}
while(!s.empty()) {
int q = s.top();
cout << a[q].name << endl;
s.pop();
}
}
}

signed main() {
ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}

本文作者:jujimeizuo
本文地址https://blog.jujimeizuo.cn/2020/10/07/hdu-1074/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!