算法核心：状态压缩DP
大意：
有n门课程作业，每门作业的截止时间为D,需要花费的时间为C，若作业不能按时完成，每超期1天扣1分。
这n门作业按课程的字典序先后输入
问完成这n门作业至少要扣多少分，并输出扣分最少的做作业顺序
PS:达到扣分最少的方案有多种，请输出字典序最小的那一组方案
分析：
n<=15，由题意知，只需对这n份作业进行全排列，选出扣分最少的即可。
用一个二进制数存储这n份作业的完成情况，第1.。。。n个作业状况分别
对应二进制数的第0，1.。。。。,n-1位则由题意，故数字上限为2^n
其中 2^n-1即为n项作业全部完成，0为没有作业完成。。。
用dp[i]记录完成作业状态为i时的信息（所需时间，前一个状态，最少损失的分数）。
递推条件如下
1.状态a能做第i号作业的条件是a中作业i尚未完成，即a&i=0。
2.若有两个状态dp[a],dp[b]都能到达dp[i],那么选择能使到达i扣分小的那一条路径，若分数相同，转入3
3.这两种状态扣的分数相同，那么选择字典序小的，由于作业按字典序输入，故即dp[i].pre = min(a,b);
初始化：dp[0].cost = 0;dp[0].pre=-1;dp[0].reduced = 0;
最后dp[2^n-1].reduced即为最少扣分，课程安排可递归的输出
第一道状压DP、上高仿代码- -
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) #define N (1<<15)+10 struct Node { int pre; //上一门课、错了，是前一个状态 int cost; //所需时间 int reduced; //最少损失的分数 }dp[N]; struct Course { char name[22]; //课程名 int deadtime; //截止日期 int cost; //完成需要的时间 }s[16]; bool vis[N]; void print(int sta) { int curjob=dp[sta].pre^sta; int curid=0; curjob>>=1; while(curjob) { curid++; curjob>>=1; } if(dp[sta].pre) { print(dp[sta].pre); } printf("%s\n",s[curid].name); } int main() { int T,i,j,n; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s%d%d",s[i].name,&s[i].deadtime,&s[i].cost); } dp[0].pre=-1; dp[0].cost=0; dp[0].reduced=0; memset(vis,0,sizeof(vis)); vis[0]=1; int up=(1<<n)-1; for(j=0;j<=up;j++) { for(i=0;i<n;i++) { int cur=1<<i; if((j&cur)==0) { int curtmp=j|cur; int day=dp[j].cost+s[i].cost; dp[curtmp].cost=day; int reduce=day-s[i].deadtime; if(reduce<0) reduce=0; reduce+=dp[j].reduced; if(vis[curtmp]) { if(reduce<dp[curtmp].reduced) { dp[curtmp].reduced=reduce; dp[curtmp].pre=j; } } else { vis[curtmp]=1; dp[curtmp].pre=j; dp[curtmp].reduced=reduce; } } } } printf("%d\n",dp[up].reduced); print(up); } return 0; }
状压DP [HDU 1074] Doing Homework
原文：http://www.cnblogs.com/hate13/p/4060519.html