hdu 1074 Doing Homework

http://acm.hdu.edu.cn/showproblem.php?pid=1074

状压dp不是很懂，看着别人的代码写的，很长时间才看懂。 dp[i]记录（1<<n）-1个状态第i状态的最小结果。用pre数组记录每一个状态的前驱。

用dfs输出路径。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 16
 5 using namespace std;
 6 const int inf=1<<29;
 7 
 8 int dp[1<<16];
 9 int t,n;
10 int pre[1<<16];
11 struct node
12 {
13     char name[110];
14     int d;
15     int c;
16 }p[maxn*10];
17 
18 void dfs(int w)
19 {
20     if(w==0) return ;
21     int pos=0;
22     for(int i=0; i<n; i++)
23     {
24         if((w&(1<<i))!=0&&(pre[w]&(1<<i))==0)
25         {
26             pos=i;
27             break;
28         }
29     }
30     dfs(pre[w]);
31     printf("%s
",p[pos].name);
32 }
33 
34 int main()
35 {
36     scanf("%d",&t);
37     while(t--)
38     {
39         scanf("%d",&n);
40         for(int i=0; i<n; i++)
41         {
42             scanf("%s%d%d",p[i].name,&p[i].d,&p[i].c);
43         }
44         for(int i=0; i<(1<<n); i++)
45         {
46             dp[i]=inf;
47         }
48         dp[0]=0;
49         for(int i=0; i<(1<<n); i++)
50         {
51             for(int j=0; j<n; j++)
52             {
53                 if(i&(1<<j)) continue;
54                 int sum=0;
55                 for(int k=0; k<n; k++)
56                 {
57                     if(i&(1<<k)) sum+=p[k].c;
58                 }
59                 sum+=p[j].c;
60                 if(sum>p[j].d) sum-=p[j].d;
61                 else sum=0;
62                 if(dp[i|(1<<j)]>dp[i]+sum)
63                 {
64                     dp[i|(1<<j)]=dp[i]+sum;
65                     pre[i|(1<<j)]=i;
66                 }
67             }
68         }
69         printf("%d
",dp[(1<<n)-1]);
70         dfs((1<<n)-1);
71     }
72     return 0;
73 }

View Code