！HDU 1074 Doing Homework-DP-（状态压缩）

！HDU 1074 Doing Homework--DP--（状态压缩）

题意：n个作业，每个作业有deadline和做完这个作业需要花的时间cost，完成作业每超过一天就减一分，求减去的最小的分数

分析：作业的全排列中取最优解，但是15！太大了会超时，所以用二进制来状态压缩，15个二进制位，第i位的0/1代表第i个作业是否完成。

         1.会用状态压缩

         2.保存和输出最优解序列方法

         慢慢加深理解吧

代码：

#include<iostream>
#include<cstring>
#include<string>
#define INF 1<<16
using namespace std;
int t,n;
struct node1{
    string chr;
	int ddl,cost;	
}a[16];
struct node2{
	int pre,reduced,days;
}dp[INF];
int vis[INF];
void Output(int i)
{
	int tmp=dp[i].pre^i;//取第i个状态时做的作业（二进制位为1的就是它）
	int cnt=0;
	tmp>>=1;//求除以2用了多少次除尽，即求得它的位置；a=b^n 求n的技巧
	while(tmp){
		cnt++;
		tmp>>=1;
	}
	if(dp[i].pre!=0) Output(dp[i].pre);//递归输出，注意递归在输出语句的前面，因为是从最后一个状态开始递归的，题目要求从前往后输出
	cout<<a[cnt].chr<<endl;	
}
int main()
{
	cin>>t;
	while(t--){
		memset(vis,0,sizeof(vis));
		cin>>n;
		for(int i=0;i<n;i++) cin>>a[i].chr>>a[i].ddl>>a[i].cost;
		dp[0].pre=-1,dp[0].days=0,dp[0].reduced=0;
		vis[0]=1;
		int en=(1<<n)-1;
		for(int i=0;i<en;i++){    //状态压缩dp
			for(int j=0;j<n;j++){
				int tmp=1<<j;
				if((i&tmp)==0){
					int tmp2=i|tmp;
					int day=dp[i].days+a[j].cost;
					dp[tmp2].days=day;
					int reduce=day-a[j].ddl;
					if(reduce<0) reduce=0;
					reduce+=dp[i].reduced;
					if(vis[tmp2]){
						if(reduce<dp[tmp2].reduced){
							dp[tmp2].reduced=reduce;
							dp[tmp2].pre=i;
						}
					}
					else{
						vis[tmp2]=1;
						dp[tmp2].reduced=reduce;
						dp[tmp2].pre=i;
					}
				}
			}
		}
		cout<<dp[en].reduced<<endl;
		Output(en);
	}
}