HDU 1074 Doing Homework (状态压缩 DP)

题目大意: 有 n 项作业需要完成，每项作业有上交的期限和需完成的天数，若某项作业晚交一天则扣一分。输入每项作业时包括三部分，作业名称，上交期限，完成所需要的天数。求出完成所有作业时所扣掉的分数最少，同时输出完成作业的顺序(若有多组结果，输出按字典序排列最小的那组)。(输入时，按名称的字典序输入)

思路 ：题目中给出的 n 的范围很小，很明显是用状态压缩来求解。将一个整数分解成二进制形式。从左往右数起，第 i 位代表第 i 项作业的完成情况，1 代表完成，0代表未完成。

  #include<iostream>

  #include<cstdio>

  #include<cstdlib>

  #include<cstring>

  #include<queue>

  #include<algorithm>

  #include<cmath>

  #include<map>

  using namespace std;

  #define INF 0x7fffffff

  struct {

   char name[102];

   int d;

   int c;

  }course[16];

  struct {

   int score;

   int day;

   int pre;

   int num;

  }dp[1 << 16];

  int main(){

   int  T,n,i,j,sum;

   cin >> T;

   while(T--){

	cin >> n;

	sum = 0;

	for(i=0;i<n;i++){

		scanf("%s%d%d",course[i].name,&course[i].d,&course[i].c);

		sum += course[i].c ;

	}

	dp[0].score = 0 ;

	dp[0].day = 0 ;

	for(i=1; i<(1<<n); i++){

		dp[i].score = INF ;

		for(j=n-1; j>=0; j--){

			if(i&(1<<j)){

				int ans = i - (1 << j);

				int reduce = dp[ans].day + course[j].c - course[j].d;

				if(reduce < 0)

				    reduce = 0 ;

				if(reduce + dp[ans].score < dp[i].score){

					dp[i].score = reduce + dp[ans].score ;

					dp[i].num = j ;

					dp[i].pre = ans ;

					dp[i].day = dp[ans].day + course[j].c ;

				}

			}

		}

	}

	printf("%d\n",dp[(1<<n)-1].score);

	char ch[16][102];

	int t = (1<<n)-1 ,top = 0 ;

	while(t){

		strcpy(ch[top++],course[dp[t].num].name);

		t = dp[t].pre;

	}

	while(top)

	    printf("%s\n",ch[--top]);

   }

   return 0;

  }