Doing Homework

2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3

2
Computer
Math
English
3
Computer
English
Math

Hint
In the second test case, both Computer->English->Math and Computer->Math->English leads to reduce 3 points, but the 
word "English" appears earlier than the word "Math", so we choose the first order. That is so-called alphabet order.
 

/*

读完题目后想的和此博客人想法大致一样
 http://www.cnblogs.com/Kenfly/archive/2011/03/30/2000364.html

可是，感觉有一个问题，因为担心会出现 a,b都可以到c 虽然a到c的花费大
，但是a可能时间短，因为此时间对后面有影响，a可能后面会反败为胜呢？

感觉这样不好处理，百度却找不到解答，最后自己想通了，原来既然状态相同，那么花费的时间是一样的，
这样疑惑顿时没有了




*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define bug printf("hihi\n")

#define eps 1e-8
typedef __int64 ll;

using namespace std;


#define INF 0x3f3f3f3f
#define N 16


struct stud{
  int pre,time;//当前状态是由哪一个点来的，当前状态时间，
  int score;//当前扣得分数
}dp[1<<16];


struct ha{
  string name;
  int d,len;
}home[N];
int n;

void show(int st)
{
    if(st==0) return ;
    show(st^(1<<dp[st].pre));
    cout<<home[dp[st].pre].name<<endl;
}
void DP()
{
   int len=1<<n;
   int i,j;
   for(i=0;i<len;i++)
        dp[i].score=INF;
   dp[0].score=0;
   dp[0].time=0;
   dp[0].pre=-1;

   for(i=0;i<len;i++)
     for(int j=0;j<n;j++)
   {
       if(i&(1<<j)) continue;
       int to=i|(1<<j);
       int time=dp[i].time+home[j].len;
       int score=0;
       if(time>home[j].d)
            score=time-home[j].d;
       score+=dp[i].score;

       if(dp[to].score>score)
       {
           dp[to].score=score;
           dp[to].pre=j;
           dp[to].time=time;
           // printf("%d: %d %d %d\n",to,to^(1<<j),dp[to].score,dp[to].time);
       }
   }
  printf("%d\n",dp[len-1].score);
  show(len-1);//递归输出路径

}

int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            cin>>home[i].name>>home[i].d>>home[i].len;//字典序输入，无需排序
        }
        DP();
    }
    return 0;
}

HDU 1074 Doing Homework（状压dp）

原文：http://blog.csdn.net/u014737310/article/details/47134165