首页 > 代码库 > HDU 1074
HDU 1074
http://acm.hdu.edu.cn/showproblem.php?pid=1074
每个任务有一个截止日期和完成时间，超过截止日期一天扣一分，问完成全部任务最少扣几分，并输出路径
最多15个任务，状态压缩一下进行dp，输出路径的话要记录每种状态的前驱，存起来逆序输出
#include <iostream>#include <cstdio>#include <cstring>#include <map>using namespace std;const int INF = 0xfffffff;struct fuck{ int w, pre;}dp[1<<15];struct node{ char name[105]; int D, C;}p[16];int cal(int x){ int res = 0, cnt = 0; while(x){ if(x & 1){ res += p[cnt].C; } cnt++; x >>= 1; } return res;}int cnt(int x){ int res = 0; while(x){ if(x & 1){ res++; } x >>= 1; } return res;}int cal1(int x, int y){ int res = 0; while(1){ if((x&1) != (y&1)){ return res; } res++; x >>= 1; y >>= 1; }}int ans[25], ct; int main(){ int T; scanf("%d", &T); while(T--){ int n; scanf("%d", &n); for(int i = 0; i < (1<<n); i++) dp[i].w = INF; int xx = 0; while(1){ dp[(1<<xx)].pre = 0; xx++; if(xx == n) break; } for(int i = 0;i < n; i++){ scanf("%s %d %d", p[i].name, &p[i].D, &p[i].C); if(p[i].C > p[i].D) dp[1<<i].w = p[i].C - p[i].D; else dp[1<<i].w = 0; } map <int, int> mp; for(int i = 0; i < (1<<n); i++){ for(int j = 0; j < n; j++){ if(i&(1<<j)){ if(cal(i) > p[j].D){ if(dp[i].w > dp[i^(1<<j)].w + cal(i) - p[j].D){ dp[i].w = dp[i^(1<<j)].w + cal(i) - p[j].D; dp[i].pre = i^(1<<j); mp[i] = i^(1<<j); } else if(dp[i].w == dp[i^(1<<j)].w + cal(i) - p[j].D && dp[i].pre > (i^(1<<j))){ dp[i].pre = i^(1<<j); mp[i] = i^(1<<j); } //dp[i] = min(dp[i], dp[i^(1<<j)] + cal(i) - p[j].D); } else{ if(dp[i].w > dp[i^(1<<j)].w){ dp[i].w = dp[i^(1<<j)].w; dp[i].pre = i^(1<<j); mp[i] = i^(1<<j); } else if(dp[i].w == dp[i^(1<<j)].w && dp[i].pre > (i^(1<<j))){ dp[i].pre = i^(1<<j); mp[i] = i^(1<<j); } //dp[i] = min(dp[i], dp[i^(1<<j)]); } } } } printf("%d\n", dp[(1<<n)-1]); int now = (1<<n) - 1; ct = 0; while(now){ ans[ct++] = cal1(now, mp[now]); now = mp[now]; } for(int i = n - 1; i >= 0; i--){ printf("%s\n", p[ans[i]].name); } } return 0;}
HDU 1074
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。