题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1074
方法：设一个数num，科目的数量为n,则将num表示成带有前导0的n位二进制数（num肯定不能超范围），在该二进制数的数位中，从左到有第i个数位是1代表第i门课的作业完成，0代笔没有，如n=4,num=6=0110代表第2和3门的作业完成，
设置状态转移方程，设F(num,k).Ans为 当完成k门课程，完成的科目是num对应的作业完成情况，这一状态下超期的最少天数。F(num,k).Beyond为 当完成k门课程，完成的科目是num对应的作业完成情况，这一状态已经超期的天数，F(num,k).Used 为 当完成k门课程，完成的科目是num对应的作业完成情况，这一状态已经使用的天数
F(num,k)=
{
[
Ans = Course[i].NeedDays - Course[i].DeadLine > 0 ?Course[i].NeedDays - Course[i].DeadLine :0 ,
Beyond = Ans,
Used = Course[i].NeedDays， k==1, num in { 2^k| 1<=k<=n-1) };
Pre = 0,
Mask = num
]
[
Ans = Min(
{
F(num1,k-1).Ans +( Course[J].NeedDays +F(num1,k-1).Used- Course[J].DeadLine > 0 ?Course[J].NeedDays+F(num1,k-1).Used - Course[J].DeadLine :0)
| num1 in {完成的k-1个作业的完成情况对应的状态二进制数} && num可以由num1的一个非1数位,第J位变成1获得 .
}
),
Beyond = Ans,
Used = Course[j].NeedDays+F(num1,k-1).Used ;这里的num1 和j 为上述Min计算选出的; k>1
Pre = F(num1,k-1).Mask ; 这里的num1为上述Min计算选出的;
Mask = num1 ;这里的num1为上述Min计算选出的;
]
}
由于字段排序的要求，当判断一个数字状态num1是不是可以由一个已经算出结果的num通过一个非1数位,第J位变成1的到的时候，在找这样的一个第j位的时候，从左往右找即可。因为题目的输入就已经是字典有序的了。
在输入构造好的最有解的时候，就是纯粹模拟了。
代码：
#include <iostream>
#include <stack>
using namespace std;
int mi[16] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
struct Course
{
char name[100];
int deadline;
int duration;
};
struct Status
{
int usedDays;
int delayDays;
int pre;
int mask;
Status()
{
mask=0;
delayDays=-1;
}
};
struct in
{
int nums[7000];
int count;
};
Course courses[16];
Status dp[33000][16];
int main()
{
int test=0,n;
cin>>test;
while(test>0)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>courses[i].name>>courses[i].deadline>>courses[i].duration;
for(int i=0;i<33000;i++)
for(int j=0;j<16;j++)
{
dp[i][j].mask=0;
dp[i][j].delayDays=8000;
}
in ins[16];
for(int i=1;i<=15;i++)
ins[i].count=0;
for(int i=1;i<=n;i++)
{
dp[mi[n-i]][1].usedDays=courses[i].duration;
dp[mi[n-i]][1].delayDays= (courses[i].duration > courses[i].deadline )? (courses[i].duration - courses[i].deadline):0;
dp[mi[n-i]][1].pre=0;
dp[mi[n-i]][1].mask=mi[n-i];
ins[1].count++;
ins[1].nums[ins[1].count]=mi[n-i];
}
for(int i=2;i<=n;i++)
{
int value;
for(int j=1;j<=ins[i-1].count;j++)
{
value = ins[i-1].nums[j];
for(int k=n;k>=1;k--)
{
if((value&mi[k-1])==0)
{
int usedDays =courses[n-k+1].duration + dp[value][i-1].usedDays;
int min = usedDays > courses[n-k+1].deadline ? (usedDays - courses[n-k+1].deadline):0;
min+=dp[value][i-1].delayDays;
if(dp[value+mi[k-1]][i].delayDays==8000)
{
ins[i].count++;
ins[i].nums[ins[i].count]=value+mi[k-1];
}
if(dp[value+mi[k-1]][i].delayDays==8000 || dp[value+mi[k-1]][i].delayDays>min)
{
dp[value+mi[k-1]][i].delayDays = min;
dp[value+mi[k-1]][i].pre = value;
dp[value+mi[k-1]][i].usedDays =usedDays;
}
dp[value+mi[k-1]][i].mask = value+mi[k-1];
}
}
}
}
cout<<dp[mi[n]-1][n].delayDays<<endl;
Status re = dp[mi[n]-1][n];
int* sts=new int[n+1];
int k=n;
while(k>=0)
{
sts[k]=re.mask;
if(k>0)
re=dp[re.pre][k-1];
k--;
}
k=0;
int t_mask;
while(k<=n)
{
if(k==0)
t_mask=sts[k];
else
{
int t = (t_mask^sts[k]);
for(int p=0;p<=15;p++)
{
if(mi[p]==t)
{
cout<<courses[n-p].name<<endl;
break;
}
}
t_mask=sts[k];
}
k++;
}
test--;
}
return 0;
}