首页 > 代码库 > HDU 1074 Doing Homework

HDU 1074 Doing Homework

2024-07-19 02:09:35   224人阅读

第一次做这道题大概是半个月前了吧，状压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


联系
我们