C語言動態規劃_Doing Homework(HDU 1074)

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;
}