连接:http://acm.hdu.edu.cn/showproblem.php?pid=1074
Doing Homework
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3973 Accepted Submission(s): 1581
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.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework).
Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework).
Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.
Output
For each test case, you should output the smallest total reduced score, then give out the order of the subjects, one subject in a line. If there are more than one orders, you should output the alphabet smallest one.
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
Hint
In the second test case, both Computer->English->Math and Computer->Math->English leads to reduce 3 points, but the
word "English" appears earlier than the word "Math", so we choose the first order. That is so-called alphabet order.
#include <cstdio> #include <iostream> #include <cstring> #include <string> using namespace std ; #define M 1<<16 int n ; bool mask[M] ; struct node{ string name ; int need_time ; int limit_time ; }work[17] ; struct state{ int use_time ; int los_time ; int father ; int res ; }sta[M] , tmp ; void print( int t ){ if( t == 0 ) return ; print( sta[t].father ) ; cout<<work[ sta[t].res ].name<<endl ; } int main(){ int T ; scanf("%d" , &T ) ; while( T -- ){ scanf("%d" , &n ) ; for( int i = 0 ; i < n ; i ++ ){ cin>>work[i].name>>work[i].limit_time>>work[i].need_time ; } memset( sta , 0 , sizeof( sta ) ) ; memset( mask , false , sizeof( mask ) ) ; int m = 1<<n ; for( int i = 0 ; i < m ; i ++ ){ for( int j = 0 ; j < n ; j ++ ) if( ( i & ( 1<<j ) ) == 0 ) { int new_i = i | ( 1<<j ) ; tmp.use_time = sta[i].use_time + work[j].need_time ; tmp.los_time = sta[i].los_time + ( ( tmp.use_time > work[j].limit_time ) ? tmp.use_time - work[j].limit_time : 0 ) ; if( mask[new_i] == false || tmp.los_time < sta[new_i].los_time ){ mask[new_i] = true ; sta[new_i] = tmp ; sta[new_i].father = i ; sta[new_i].res = j ; } } } printf("%d\n" , sta[m-1].los_time ) ; print( m-1 ) ; } return 0 ; }
相关推荐
HDU的一题........HDU DP动态规
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码