HDU 1074 Doing Homework （状态压缩DP）

#include<iostream>

#include<string.h>

#include<stdio.h>

#define N (1<<15)+5

#define M 120

#define INF 0x3f3f3f3f

using namespace std;

int dp[N];//dp[i]表示状态i时最少扣的分数

struct node

{

	char name[M];

	int d,c;//截止日期，花费时间

}a[20];

int path[N];//path[i]=k表示i状态是由k状态转移过来的

int t,n;

/*

打印路径就是在状态转移的时候用一个数组记录下来，一个状态是由哪一个状态成功转移过来的，然后最后打印路径的时候就是反着这个根据用递归输出出来就行了

*/

void print(int x)

{

	if(x==0)

		return;

	int t=0;

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

	{

		if( (x&(1<<i)) !=0 && (path[x]&(1<<i)) ==0 )//有这个状态有交际，并且能补全上一个状态

		{

			t=i;

			break;

		}

	}

	print(path[x]);

	printf("%s\n",a[t].name);

}

/*

状态的转移：先枚举二进制的状态，每枚举到一个状态的时候，在这个状态中遍历所有课程，若这门课程完成了那么已经包括在这个状态中了，如果没完成就要

像01背包那样讨论完成和不完成的罚时到底哪个小，假如现在不完成的罚时小，那么这门课就先不完成，后面在完成。

*/

int main()

{

	//freopen("in.txt", "r", stdin);

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d\n",&n);

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

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

		memset(dp,INF,sizeof dp);

		memset(path,0,sizeof path);

		dp[0]=0;//什么课也没开始上罚时当然是0了

		int tol=(1<<n);

		for(int i=0;i<tol;i++)//枚举状态

		{

			for(int j=n-1;j>=0;j--)//枚举那门课

			{

				if((i&(1<<j))==0)//这门课上没上，找出每一个当前功课没完成的状态，然后由这个状态转移到完成了当前课程的状态

				{

					int s=0;

					for(int k=0;k<n;k++)//计算这个状态到现在花费的时间

						if(i&(1<<k))//这门课上了

						s+=a[k].c;

					s+=a[j].c;//再加上j这门课花费的时间

					int time=s-a[j].d;//计算罚时

					if(time<0)

						time=0;

					if(dp[i|(1<<j)]>dp[i]+time)

					{

						dp[i|(1<<j)]=dp[i]+time;

						path[i|(1<<j)]=i;//如果这个状态转移过来了，就记录下来是由哪个状态转移过来的

					}

					//cout<<dp[i|(1<<j)]<<endl;

				}

			}

		}

		//for(int i=0;i<tol;i++)

		//	cout<<path[i]<<" ";

		//cout<<endl;

		printf("%d\n",dp[tol-1]);

		print(tol-1);

	}

	return 0;

}