*HDU1074.Doing Homework(状压DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074
题意：给出n个课程，每个课程给出课程名称、截止日期、完成需要的时间，超过截止日期完成的课程每超过一天减少分数1。求最少减少的分数方案，如果有多个方案，输出字典序最小的方案
解题思路：因为n最大是15，可以使用二进制来进行状压DP讨论。
dp结构体:

struct plan{
	int pre;     //记载上一个状态
	int choice;  //记录当前状态选择的课程
	int time;    //记录当前课程完成需要的时间
	int score;   //记录减少的得分
}dp[(1<<15)+10];

dp主体部分：

for(int i=1;i<=end;i++){
			dp[i].score=99999999;
			for(int j=n-1;j>=0;j--){   //从后往前遍历
				int tmp=1<<j;
				if(i&tmp){
					int ttmp=i-tmp;
					 //计算超时多少
					int tmp_cost=dp[ttmp].time+hw[j].c-hw[j].d;  
					//如果超时不为正数，则扣分为0
					if(tmp_cost<0) tmp_cost=0;
					if(tmp_cost+dp[ttmp].score<dp[i].score){
						dp[i].score=tmp_cost+dp[ttmp].score;
						dp[i].time=dp[ttmp].time+hw[j].c;
						dp[i].pre=ttmp;
						dp[i].choice=j;
					}
				}
			}
		}

递归输出：

void print(int pos){
	if(pos==0)
		return ;
	print(dp[pos].pre);
	cout<<hw[dp[pos].choice].name<<endl;
	return ;
}

#include<cstdio>
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int t;
int n;
struct node{
	string name;
	int d,c;
}hw[30];
struct plan{
	int pre;
	int choice;
	int time;
	int score;
}dp[(1<<15)+10];
void print(int pos){
	if(pos==0)
		return ;
	print(dp[pos].pre);
	cout<<hw[dp[pos].choice].name<<endl;
	return ;
}
int main(){
	cin>>t;
	while(t--){
		memset(dp,0,sizeof(dp));
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>hw[i].name;
			cin>>hw[i].d>>hw[i].c;
		}
		int end=(1<<n)-1;
		for(int i=1;i<=end;i++){
			dp[i].score=99999999;
			for(int j=n-1;j>=0;j--){
				int tmp=1<<j;
				if(i&tmp){
					int ttmp=i-tmp;
					int tmp_cost=dp[ttmp].time+hw[j].c-hw[j].d;
					if(tmp_cost<0) tmp_cost=0;
					if(tmp_cost+dp[ttmp].score<dp[i].score){
						dp[i].score=tmp_cost+dp[ttmp].score;
						dp[i].time=dp[ttmp].time+hw[j].c;
						dp[i].pre=ttmp;
						dp[i].choice=j;
					}
				}
			}
		}
		cout<<dp[end].score<<endl;
		print(end);
	}
	return 0;
}

本文地址：https://blog.csdn.net/littlegoldgold/article/details/107297188