传送门: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++)
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); ##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 协议。转载请注明出处!