首页 > 代码库 > HDU - 1074 Doing Homework
HDU - 1074 Doing Homework
题意:学生有多个任务,每个任务有规定完成的时间,还有完成的时间,超过规定一天就扣一分,求最少的扣分,相同的话,按字典序
思路:DP的状态搜索,每次枚举一个,然后从第一个开始匹配,因为题目已经排序了,所以不用考虑这个字典序最小了,对于每次新加进来的,如果超过规定时间就计算多出来的,没有的话,就是0了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 20; const int INF = 0x3f3f3f3f; struct Node { char name[200]; int D,C; }node[MAXN]; int dp[1<<MAXN]; int pre[1<<MAXN]; int n; void print(int s) { if (s == 0) return; int cnt = 0; for (int i = 0; i < n; i++) if ((s&(1<<i)) != 0 && (pre[s]&(1<<i)) == 0) { cnt = i; break; } print(pre[s]); printf("%s\n", node[cnt].name); } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%*c", &n); for (int i = 0; i < n; i++) scanf("%s%d%d", node[i].name, &node[i].D, &node[i].C); for (int i = 0; i < (1<<n); i++) dp[i] = INF; dp[0] = 0; for (int i = 0; i < (1<<n); i++) { for (int j = 0; j < n; j++) { if (i & (1<<j)) continue; int cnt = 0; for (int k = 0; k < n; k++) if (i & (1<<k)) cnt += node[k].C; cnt += node[j].C; if (cnt > node[j].D) cnt -= node[j].D; else cnt = 0; if (dp[i|(1<<j)] > dp[i]+cnt) { dp[i|(1<<j)] = dp[i]+cnt; pre[i|(1<<j)] = i; } } } printf("%d\n", dp[(1<<n)-1]); print((1<<n)-1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。