HDU1074：Doing Homework(状态压缩DP)

最新推荐文章于 2021-08-30 14:52:22 发布
最新推荐文章于 2021-08-30 14:52:22 发布
阅读量3.6w 收藏 7
点赞数 1
谢绝转载-https://update.blog.csdn.net
本文链接：https://blog.csdn.net/update7/article/details/74858456
版权
编程. 同时被 2 个专栏收录
578 篇文章 ¥299.90 ¥399.90
订阅专栏
编程..
570 篇文章 ¥299.90 ¥399.90
订阅专栏
该博客探讨了一种优化作业顺序的问题，旨在在有限的课程中找到最佳完成顺序，以尽量减少因超期完成作业而产生的扣分。通过使用状态压缩动态规划的方法，可以解决这个问题，尤其适用于最多15门课程的情况。

摘要生成于 C知道 ，由 DeepSeek-R1 满血版支持， 前往体验 >

Problem Description
Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.
 
了解本专栏 订阅专栏 解锁全文
HDU 1074 Doing Homework（DP·状态压缩）
Deng's site \#
08-28 2080
题意  有n个作业要做   给你每个作业的最后期限  和做完这个作业需要的时间  作业每超过最后期限一天就会扣一分  只能把一个作业做完了再做另一个作业  问做完所有作业至少扣多少分 作业最多只有15个  看到这个数字容易想到是状态压缩  dp[i]表示i对应状态的最小扣分  i转换为二进制后为1的位表明该位对应的作业已经做了  为0的位没做  那么dp[i] = min{dp[k] + c
hdu 动态规划（46道题目）倾情奉献~ 【只提供思路与状态转移方程】(转)
Pegasus (http://ningning.today)
09-01 2352
HDU 动态规划（46道题目）倾情奉献~ 【只提供思路与状态转移方程】 Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955      背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱  最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=max{f[j],
hdu_1074
java开发指南博客 【转载】
11-22 188
这道题不难，但是做出来了还是觉得很有成就感，首先是以前不会状态dp，第二是这几天温度变化太大，自己状态不怎么好。。。唉，看图论看的快疯了。。早上起来发现做的梦都是关于图论的。。啊！！图论坑爹啊。。T T。。学了一下之后才知道，原来状态dp利用的思想就是离散数学里格的思想，他本质上就是一个n阶的布尔代数，拥有一切布尔代数的性质，所有的状态可以唯一表示为n个原子的集合，这也是证明这种dp正确性必不可少...
Doing homework 状态压缩dp
flowingfish的博客
01-29 144
#include <iostream> #include <stack> #include <algorithm> using namespace std; const int inf = 1<<30; struct node { string name; int dead,cost;
Doing Homework——状态压缩dp
小白之比白更白的博客
09-12 289
Problem Description Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce
hdu1074
linxingqianglai的专栏
09-07 1400
hdu1074
kuangbin专题十二 基础dp
qq_43657674的博客
08-30 368
kuangbin专题十二 基础dp 1. Max Sum Plus Plus 压缩一维避免超空间，维护前缀最大值将O(n3)O(n^3)O(n3)降到O(n2)O(n^2)O(n2)。 #include<bits/stdc++.h> using namespace std; const int N=1e6+10,INF=0x7fffffff; int n,m; int a[N],f[N],Max[N]; int main() { while(scanf("%d%d",&m,&am
Kuangbin 第12套 基础DP部分题题解
Untersee-boot XXI
10-10 930
1.Max sum plus plus 本题是一个M段子段的最大字段和的问题，也就是把一个数列分成M小节使得每小节总和最大。关于这个问题先从最大子段和（单段）开始说起。 最大子段和（子段是连续子数列）的求解意味着对于数列中一个元素，要么归于前面已经成型的一个子段，要么自成一派创立新的子段。这个抉择取决于这两个的权值的大小，如果成型的子段的和较大，那么就让它加入前面的子段，否则就自己作为新子段的...
HDU 1074
mowenwen_的博客
07-19 727
题意：给出了一堆科目，必须要完成的时间和完成某科所需要的时间，超过一天扣一分，求最少要扣的分数。 思路：刚开始一直以为是贪心，却一直贪不出来~~ 看了别人的题解，才顿悟啊~ 状压DP，用二进制来表示某个科目的完成状态。 比如样例一： 用111表示三科都完成了，101表示第一科和第三科完成了，这样就很easy~\(≧▽≦)/~啦啦啦。 for(int i=1;i for(int j=n-1;
HDU 1074(状压dp)
smilestruggler_Fly To Higher
02-08 284
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074   题目大意：给一堆作业的ddl和所需完成时间，如果超时就要多花1的代价，问最后最少需要花多少代价，并输出完成作业的顺序。   题目思路：状压dp，用连续15位表示作业完成情况，1为做了，0为没做，然后从1到(1&lt;&lt;n)-1，通过思考可以发现，多数字的情况出现时，比它少一个数...
HDU-1074(状压DP）
qq_44641782的博客
01-11 271
Problem Description Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in t...
HDU1074(状压DP)
开心铁匠铺
04-11 470
题目链接 题意：有n门课，每门课都要交作业，作业有时间花费和最晚提交日期，如果超过日期交作业，每超过一天就要扣一分，问最少扣多少分并且给出最少扣分的方案。 题解： 因为最多只有15门课，所以可以压缩成一个数，二进制位上每一位代表一门课是否完成。然后开始DP。 枚举从1到1&lt;&lt; n的每一个状态i，然后枚举每一门课j（倒叙枚举，因为输入是按照字典序递增输入的），检查状态i是否完成了...
HDU 1074 (状态压缩DP)
Night__elf
12-26 470
http://acm.hdu.edu.cn/showproblem.php?pid=1074 题意：给出n（n 　　由数据规模可以知道可以用状态压缩DP来解决。一般的DP题目都可以用搜索和递推两种方法解决，这道题来说，递推思路会比较直观，而递推的时间效率高很多! 　　用搜索来解决，主要要注意两个地方，一是状态的转移，二是剪枝。由状态0开始进行DFS，每次添加一个当前还没有安排的
树型动态规划详解：从状态压缩到树形DP
在处理具有大量状态但状态之间关系简单的问题时，状态压缩DP非常有效。 总结来说，树型动态规划是解决树结构问题的重要工具，它通常从叶节点开始，逐层向上进行状态转移，构建全局最优解。状态压缩DP则是动态规划的...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值