hdu1074 参考答案

   1 /*
   2 hdu1074
   3 ymc 2008/10/9
   4 题目大意
   5 你n个任务，每个任务完完成的最后期限d和所需的时间c。
   6 如果某个任务的完成时间超过了最后期限d，则要惩罚，惩罚的数值为超过的天数。
   7 求完成这n个任务的最小惩罚数值以及完成的次序。
   8 分析与解题思路：
   9 用n位表示任务的完成状态，对应位上为1表示该任务已经完成，否则表示未完成。
  10 每个状态有三个数据，分别是达到该状态的最小惩罚数值，达到该状态总共所需的时间，已经到达该
  11 状态的最后完成个一个任务。
  12 结构体
  13 struct Status
  14 {
  15     int reduce; //惩罚时间
  16     int time;//总共花费时间
  17     int last;//最后一个完成的任务
  18 };
  19 Status ans[M]表示所有的状态
  20 则状态转移方程为
  21 ans[next].reduce=min{ans[k].reduce+reduce[i]};
  22 其中k为第i个任务未完成，完成的i个任务后，状态k转变为状态next。
  23 */
  24 #include <iostream>
  25 #include <limits>
  26 using namespace std;
  27 const int N=15;
  28 const int M=65536;
  29 char s[N][110];
  30 int d[N],c[N];
  31 int n;
  32 struct Status
  33 {
  34     int reduce; //惩罚时间
  35     int time;//总共花费时间
  36     int last;//最后一个完成的任务
  37 };
  38 Status ans[M];
  39 void Init()
  40 {
  41     scanf("%d",&n);
  42     for(int i=0;i<n;i++)
  43         scanf("%s %d %d",s[i],&d[i],&c[i]);
  44    memset(ans,-1,sizeof(ans));
  45 }
  46 void DP()
  47 {
  48     ans[0].time=0;
  49     ans[0].reduce=0;
  50     int max=(1<<n)-1;
  51     int next;
  52     for(int k=0;k<max;k++)
  53     {
  54         if(ans[k].reduce==-1)
  55             continue;
  56         for(int i=0;i<n;i++)
  57         {
  58             int tmp=(k>>i);
  59             if((tmp&1)==0)//第i个任务未完成
  60             {
  61                 next=k+(1<<i);
  62             }
  63             else
  64                 continue;
  65             ans[next].time=ans[k].time+c[i]; //完成第i个任务
  66             tmp=ans[k].reduce;
  67             if(ans[next].time>d[i])
  68                 tmp+=ans[next].time-d[i];
  69             if(ans[next].reduce==-1||ans[next].reduce>tmp)
  70             {
  71                 ans[next].reduce=tmp;
  72                 ans[next].last=i;
  73             }
  74         }
  75         ans[k].reduce=-1;//当前状态以后不会在用到。
  76     }
  77 }
  78 void Output()
  79 {
  80     int t;
  81     t=(1<<n)-1;
  82     printf("%d\n",ans[t].reduce);
  83     int out[N];
  84     int k=0;
  85     while(ans[t].last>=0)//生成输出序列
  86     {
  87         out[k++]=ans[t].last;
  88         t=t-(1<<ans[t].last);
  89     }
  90     for(int k=n-1;k>=0;k--)
  91         printf("%s\n",s[out[k]]);
  92 }
  93 int main()
  94 {
  95     int test;
  96     scanf("%d",&test);
  97     while(test-->0)
  98     {
  99         Init();
 100         DP();
 101         Output();
 102     }
 103 }