HDU1074 Doing Homework

HDU1074 Doing Homework 状压DP

题意思路Code（15MS）

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

题意

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

思路

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

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

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

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

Code（15MS）

#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; }