hdu 1074 Doing Homework(状压dp)

传送门：hdu 1074

题意：有n个作业，每个作业都有最迟上交时间和完成该作业所需的时间，若某作业超过最迟上交时间，则扣相应的分数，求上交所有的作业使得扣分最少，并输出作业的顺序，若扣分相同，则先交字典序较小的作业。（n<=15)

分析：每种作业都有已上交和未上交两种，状态，总共有2^15种状态，用二进制表示。

由于要记录扣分，当前时间和作业的顺序，所以定义一个结构体。

状态表示：dp[i].ans表示扣分

dp[i].now表示当前时间

dp[i].pre表示上一个状态

状态转移：(1)状态dp[sta]能上交作业j的条件是作业j还没上交，即sta&(1<<j)==0，此时状态变为dp[sta|(1<<j)]

(2)若状态dp[x]和dp[y]都能到达状态dp[k],则应选择扣分最小的那条路径，即dp[k].ans=min(dp[k].ans,cost)，其中cost为上一个状态变为状态k时所需的花费，若扣分相等则转(3)

(3)若扣分相等，则选字典序最小的路径

状态初始化：dp[i].ans=0,dp[i].now=0,dp[i].pre=-1

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define INF 0x3f3f3f3f
 4 struct HomeWork{
 5     char s[105];
 6     int deadline,day;
 7 }homework[20];
 8 struct DP{
 9     int pre,ans,now;
10 }dp[2<<15];
11 int n;
12 int name[20];
13 void print()
14 {
15     printf("%d
",dp[(1<<n)-1].ans);
16     int i,k,num,j,cnt=0;;
17     i=(1<<n)-1;
18     while(dp[i].pre!=-1)
19     {
20         k=i^dp[i].pre;
21         for(j=0;j<n;j++)
22             if(k==(1<<j))
23             {
24                 num=j;
25                 break;
26             }
27         name[cnt++]=num;
28         i=dp[i].pre;
29     }
30     for(i=cnt-1;i>=0;i--)
31         printf("%s
",homework[name[i]].s);
32 }
33 int min(int a,int b)
34 {
35     return a<b?a:b;
36 }
37 int main()
38 {
39     int t,i,j,k,tmp,cost,sta;
40     scanf("%d",&t);
41     while(t--)
42     {
43         scanf("%d",&n);
44         for(i=0;i<n;i++)
45         {
46             scanf("%s%d%d",homework[i].s,&homework[i].deadline,&homework[i].day);
47         }
48         for(i=0;i<(1<<n);i++)   //初始化
49         {
50             dp[i].ans=0;
51             dp[i].now=0;
52             dp[i].pre=-1;
53         }
54         for(sta=0;sta<(1<<n);sta++)    //枚举所有状态
55         {
56             for(j=0;j<n;j++)
57             {
58                 i=sta&(1<<j);    //作业j还没做
59                 if(i==0)
60                 {
61                     k=sta|(1<<j);   //新状态k
62                     tmp=dp[sta].now+homework[j].day;
63                     if(dp[k].now==0)   //状态k第一次出现
64                     {
65                         dp[k].now=tmp;
66                         if(homework[j].deadline<tmp)
67                             cost=tmp-homework[j].deadline;
68                         else
69                             cost=0;
70                         dp[k].ans=dp[sta].ans+cost;
71                         dp[k].pre=sta;
72                     }
73                     else
74                     {
75                         if(homework[j].deadline<tmp)   //状态sta转为k的花费
76                             cost=tmp-homework[j].deadline;
77                         else
78                             cost=0;
79                         cost+=dp[sta].ans;
80                         if(cost==dp[k].ans)     //若扣分相等，则选择字典序最小的路径
81                         {
82                             dp[k].pre=min(dp[k].pre,sta);
83                         }
84                         else
85                         {
86                             if(cost<dp[k].ans)   //选择扣分最小的路径
87                             {
88                                 dp[k].ans=cost;
89                                 dp[k].pre=sta;
90                             }
91                         }
92                     }
93                 }
94             }
95         }
96         print();
97     }
98     return 0;
99 }

View Code