首页 > 代码库 > HDU 1074 Doing Homework
HDU 1074 Doing Homework
第一次做这道题大概是半个月前了吧,状压DP一个很新鲜的名词
当时看题解怎么也看不懂,现在看懂了以后还是很简单的
所谓状态压缩就是用一个整数的二进制来表示一个状态,比如有三个作业
000表示一科作业也没做,001表示只做了第一科,111表示三科作业都做了
那么从状态0开始出发,遍历每一个状态,如果对于状态S有第i科作业没写那么计算该状态下做完第i科作业对应的扣分数,如果比别人状态下转移过来的扣分数要少,那么状态S就是下一个状态的前驱
用结构体里的pre来保存路径
最后输出科目的时候用递归输出,也是一种很常用的方法
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 5 const int maxn = (1 << 16); 6 struct Node 7 { 8 int used; 9 int pre;10 int reduced;11 }dp[maxn];12 13 struct Course14 {15 int deadline;16 int cost;17 char name[202];18 }course[16];19 20 bool vis[maxn];21 22 void OutPut(int S)23 {24 int t = S ^ dp[S].pre;25 int i = -1;26 while(t)27 {28 t >>= 1;29 ++i;30 }31 if(dp[S].pre != 0)32 OutPut(dp[S].pre);33 printf("%s\n", course[i].name);34 }35 36 int main(void)37 {38 #ifdef LOCAL39 freopen("1074in.txt", "r", stdin);40 #endif41 42 int T;43 scanf("%d", &T);44 while(T--)45 {46 int n;47 scanf("%d", &n);48 for(int i = 0; i < n; i++)49 scanf("%s%d%d", course[i].name, &course[i].deadline, &course[i].cost);50 memset(vis, false, sizeof(vis));51 vis[0] = true;52 dp[0].used = 0, dp[0].pre = -1, dp[0].reduced = 0;53 int All = (1 << n) - 1;54 for(int S = 0; S < All; ++S)55 for(int i = 0; i < n; ++i)56 {57 if((S & (1 << i)) == 0)58 {//S状态下第i项作业还没做59 Node temp;60 int next = S | (1 << i);61 temp.used = dp[S].used + course[i].cost;62 temp.pre = S;63 temp.reduced = temp.used - course[i].deadline;64 if(temp.reduced < 0) temp.reduced = 0;65 temp.reduced += dp[S].reduced;66 67 if(vis[next] && temp.reduced < dp[next].reduced)68 dp[next] = temp;69 else if(!vis[next])70 {71 vis[next] = true;72 dp[next] = temp;73 }74 }75 }76 77 printf("%d\n", dp[All].reduced);78 OutPut(All);79 }80 return 0;81 }
HDU 1074 Doing Homework
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。