博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 1074 Doing Homework 状压DP
阅读量:5347 次
发布时间:2019-06-15

本文共 2315 字,大约阅读时间需要 7 分钟。

题目链接:

巨恶心。找了一晚上bug,发现for循环初始化居然不能代替memset。真心不服、

附AC代码:

1 #include 
2 #include
3 #include
4 using namespace std; 5 6 #define N 16 7 #define M 1<<16 8 #define inf 0x3f 9 int n, m;10 int dp[M], pre[M], t[M];11 int dead[N], cost[N];12 char name[N][210];13 14 void print(int t) {15 if (t == 0) return;16 print(pre[t]);17 t -= pre[t]; //18 for (int i=0; i
t[i] ? 0 : t[i] - dead[j];50 if (dp[k] + tcost <= dp[i]) { //从前往后枚举的,应该是没有等于号会是字典序从小到大啊。???51 dp[i] = dp[k] + tcost;52 pre[i] = k;53 }54 }55 }56 printf("%d\n", dp[m-1]);57 print(m-1);58 }59 return 0;60 }
View Code

附详解代码:

1 /* 2  题意:给出n(1<=n<=15)个作业,和该作业的dealline 和 完成所需时间。作业晚交一天就会扣1分。 3  要知道完成所有任务使减少的分数最少的完成方案。如果方案数有多个,输出字典序最小的。作业名称长度不会超过100个字符。 4  5  //思路:从当前时间为0开始,寻找最紧迫的作为下一个要完成的目标,直到所有的任务完成。 6  当前最需要完成的应该是dealine-tasktime当前时间差最少的。也就是可以按照deadine-tasktime,从小到大排序。依次完成。 7  //以上出自无厘头。虽然也并没有验证这样为什么不对、 8  9  思路:状压DP。因为N最大是15.所以用一个数m,2^15表示总的状态。变成二进制时0和1分别表示当前作业没做和做了。从0到m的每一个状态,10  遍历每一个作业在当前状态下是否已经完成,如果没有,继续下一个作业。否则,比较当前状态没有完成该作业到完成该作业减少的时间和原来需要的时间,取最小值。11  dp[i] = j。表示i状态下减少时间最少是j。T_T说不清楚。具体见代码吧。。12  */13 14 #include 
15 #include
16 #include
17 using namespace std;18 19 const int N = 16, M = 1 << N;20 21 int d[N], c[N], n;22 int dp[M], pre[M], t[M];23 char s[N][105];24 25 void print(int k)26 {27 if(k == 0) return;28 print(pre[k]);29 k -= pre[k];30 for(int i = 0; i < n; ++i)31 if(k & 1 << i) puts(s[i]);32 }33 34 int main() {35 int T, m, cost;36 scanf("%d", &T);37 while(T--) {38 scanf("%d", &n);39 for (int i=0; i
<< n; // 0到m 表示所有的状态46 47 for (int i=1; i
d[j] ? t[i] - d[j] : 0; //和j作业的截止时间对比,得出当前减少的时间54 if (dp[k] + cost <= dp[i]) { //判断是不是要从k到i。55 dp[i] = dp[k] + cost;56 pre[i] = k;57 }58 }59 }60 printf("%d\n", dp[m-1]);61 print(m-1);62 }63 return 0;64 }
View Code

 

转载于:https://www.cnblogs.com/icode-girl/p/5188480.html

你可能感兴趣的文章
java 服务重启 js 中被注释代码仍然执行
查看>>
我并不是不闻不问![C#]
查看>>
web前端经典小题
查看>>
AutoCAD如何倒角 倒圆角 倒直角
查看>>
Office PPT中如何插入flash
查看>>
C# Fade Form Effect With the AnimateWindow API Function
查看>>
golang多维数组的切片
查看>>
IP 网际协议
查看>>
C语言_第五章__实践(密码转换)
查看>>
docker 容器后台运行命令
查看>>
jquery 获取css position的值
查看>>
面向对象的程序设计
查看>>
a标签添加点击事件
查看>>
Context.startActivity出现AndroidRuntimeException
查看>>
Intellij idea创建javaWeb以及Servlet简单实现
查看>>
代理网站
查看>>
Open multiple excel files in WebBrowser, only the last one gets activated
查看>>
FFmpeg进行视频帧提取&音频重采样-Process.waitFor()引发的阻塞超时
查看>>
最近邻与K近邻算法思想
查看>>
【VS开发】ATL辅助COM组件开发
查看>>