C语言动态规划_Doing Homework(HDU 1074)

 

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.

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 

 

题意:

现在你要有很多样作业要赶,每样作业老师给的规定时间和你实际需要的时间不全一样,但是你不能同时做两样作业.如果其中一样作业不能按时交,那么每延后一天就扣一分,当然对于每样作业也是如此,现在要你确定一种写作业的顺序使得扣分最少.

每项样例数据 第一行为整数n,表示还有n样作业需要做,接下来n行分别是每样作业的名称,规定时间以及实际需要时间.(注意:题目中输入的作业名称都是按首字母字典顺序排列的)

要求输出第一行为最少扣的分,接下来n行是你做作业的顺序,如果有两种顺序扣分一样都是最少,那么输出顺序按作业名称首字母字典顺序.

 

这道题因为每样作业都不样,所以状态量太多.不好写状态转移方程式.

这里我们涉及到一个新的dp思想————状态压缩dp

这里由于每道题不一样不能简单的直接 由 作业做完的个数作为状态量来递推,这里我们要分类到每样作业的完成情况作为状态.由于作业的状态只有两种——做完和没做,那么我们就用二进制作为状态标记.比如二进制的 101 就表示第一样和第三样作业做完了,第二样作业没做.那么十五样作业用 0 ~ 1<<15-1 可以全部枚举完.

 

状态压缩状态表示主要是用二进制,那么就设计到位运算的一些技巧:

 

1.获取一个二进制数的一个或几个固定位置的值.

假设 x = 1010 (十进制的10) 我们要获取x右边起第二个数的值那么我们可以这样 : x & (1<<1) 然后判断这个的值是否等于0就可以知道 x右边起的第二位是0还是1了.

到 x 右边起的 k 位 ( x >= 1<

同样我们 可以通过判断 x & (3<<2) 的值可以得到 x右边起第3,4位的值.

2.把一个二进制数的一个或几个固定位置置零.

把 x 的右边起第k个数置零 x = x & ( ~( 1<< (k-1) ) ).

同样 x = x & (~( 3<<2 ) ) 可以把 x 右边起第3、4位置零

3.把一个二进制的一个或几个固定位置取反.

把 x 的右边起第k个数取反. x = x ^ (~ ( 1<<(k-1) ) ) ;

同样 x = x ^ (~( 3<<2 ) ) 可以把 x 右边起第3、4位取反

 

在这道题中. 我们可以知道 状态 j = i - (1 << k) 的话,那么状态 i 一定是由 j 通过 第 k 样作业完成到达的.也并且 i > j .那么我们在递推第 i 状态的时候,他的前一状态 j 一定是计算过的.满足了无后效性那么我们就可以用dp来做这道题了.

 

上代码：

 

#include   
#include   
#include 
#define inf 9999999
using namespace std;
const int max=1<<15+1;
int dp[max],t[max],pre[max],all_t[20],fin_t[20]; //dp [i] 是 i 状态下的最小扣分. t [i]是 i 状态下的所花时间. pre [i] 就是到达 i 状态的前驱作业编号.
char str[20][110];
void out(int x)
{
	if(!x) return;
	out(x-(1<
=0;j--){  //这里之所以逆序,是因为输出要按字典顺序,在这里 i-1<< j 通过j到达i状态,那么 i - 1<< j 一定比 j 先计算.其实就是 j 是后到达的.这个要自己悟.不好描述.
				int step=1<dp[i-step]+score){
					dp[i]=dp[i-step]+score;
					t[i]=t[i-step]+fin_t[j];
					pre[i]=j;
				}
			}
		}
		printf("%d\n",dp[tot-1]);
		out(tot-1);
	}
	return 0;
}
[x]));>