博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 1074 Doing Homework (dp+状态压缩)
阅读量:5098 次
发布时间:2019-06-13

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

题目链接:

题目大意:学生要完成各科作业, 给出各科老师给出交作业的期限和学生完成该科所需时间, 如果逾期一天则扣掉一单位学分, 要你求出完成所有作业而被扣最小的学分, 并将完成作业的顺序输出.

Sample Input
2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3
 
Sample Output
2
Computer
Math
English
3
Computer
English
Math

分析:(转)

刚开始以为是背包, 但背包难以记录输出顺序, 所以只能换另一种DP方式, 这里科目最大数目才15, 只要有全枚举的思想来DP就可以解决了, 有一个专有名词叫状态压缩DP. 状态压缩DP采用二制进的思想,

      1, 0分别代表有或否.

    如:

    3的二进制为 11, 则代表完成了每一,二个科目的状态, 101代表完成了第一三两个科目的状态.

    这样, 可以从0->(1 << N)来获取所有状态, 并进行适当的状态转移. 对该题来说 D[s]代表集合s的状态,  要得到D[s]的状态, 可以从0 - N 分别检查是否在s集合内[s & (1 << i) > 0则表示i在集合s上,反之..], 如果i在s集合内, 刚D[s]可从D[s-{i}]来获得, [s-{i},可以s - (1<<i)来计算]. 这样表示在已完成了s-{i}的基础上再完成i后的装态, 遍历i, 取最优解.

代码如下:

 

1 # include
2 # include
3 # include
4 # include
5 # include
6 using namespace std; 7 const int MAXN = 16; 8 const int INF = 0xffffff; 9 struct Homework{10 string name;11 int deadline; //截止时间12 int time; //完成时间13 }data[MAXN];14 15 struct {16 int time; //完成该集合作业所需时间17 int score; //完成该集合作业被扣学分18 int last; //记录上一个位置19 int pos; //记录当前位置20 }dp[1<
>T;26 while(T--){27 cin>>n;28 for(i=0;i
>data[i].name>>data[i].deadline>>data[i].time;30 int endstate = 1<
=0;i--){38 recent = 1<
path; //保存路径55 recent = endstate - 1; //1<

 

 

 

 

 

转载于:https://www.cnblogs.com/acm-bingzi/p/3278900.html

你可能感兴趣的文章
sql语句+model.id+
查看>>
北漂中~
查看>>
Learning Cocos2d-x for XNA(7)——让Sprite动起来
查看>>
Oracle部署安装
查看>>
制作Java安装程序
查看>>
学习before和after伪元素
查看>>
L1-039. 古风排版
查看>>
MSSQL → 06:T-SQL语言基础
查看>>
JavaScript中valueOf函数与toString方法深入理解
查看>>
Python(二十九)
查看>>
SQLite可视化管理工具汇总
查看>>
js 清空html input file的值
查看>>
activeInHierarchy 与 activeSelf 的区别
查看>>
44. Wildcard Matching(dp、动态规划)
查看>>
mysql写注释的几种方法
查看>>
不安装Oracle客户端,用plsql连接远程Oracle数据库(绝对解决你的问题)
查看>>
hao123劫持主页
查看>>
c# 方法参数 params 的试用
查看>>
Ibatis 美元符号替换为井号
查看>>
异或最大值
查看>>