首页 > 代码库 > 状态压缩-----HDU1074 Doing Homework

状态压缩-----HDU1074 Doing Homework

2024-07-17 20:01:16   217人阅读

         HDU1074 Doing Homework

　　

　　题意：给了n个家庭作业，然后给了每个家庭作业的完成期限和花费的实践，如果完成时间超过了期限，那么就要扣除分数，然后让你找出一个最优方案使扣除的分数最少，当存在多种方案时，输出字典序最小的那种，因为题意已经说了家庭作业的名字是按照字典序从小到大输入的，所以处理起来就好多了。

分析：此题的关键是如何记录路径，具体看代码

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5  6 using namespace std; 7 #define MAX 1<<15+1 8 int N; 9 struct Node{10 char name[108];11 int deadline;12 int cost;13 }homework[16];14 struct START15 {16     int time;17     int pre;18     int score;19     int now;20 } dp[MAX];21 int record[16];22 23 void DP()24 {25     int Final=(1<<N)-1,punish,previous;26     dp[0].id=dp[0].now=dp[0].pre=dp[0].score=dp[0].time=0;27     for(int i=1;i<=Final;i++)28     {29         dp[i].score=10000000;30         for(int j=0;j<N;j++)31             if(i&(1<<j))32         {33              previous=(i-(1<<j));34             if(dp[previous].time+homework[j].cost>homework[j].deadline)35                 punish=dp[previous].time+homework[j].cost-homework[j].deadline;36             else punish=0;37             if(dp[i].score>=dp[previous].score+punish)38             {39                 dp[i].score=dp[previous].score+punish;40                 dp[i].time =dp[previous].time+homework[j].cost;41                 dp[i].pre=previous;42                 dp[i].now=j;43             }44         }45     }46     printf("%d\n",dp[Final].score);47     int cal=Final,num=0;48     while(cal)49     {50         record[num++]=dp[cal].now;51         cal=dp[cal].pre;52     }53     for(int i=num-1;i>=0;i--)54     puts(homework[record[i]].name);55 56 }57 int main()58 {59    int T;60    scanf("%d",&T);61    while(T--)62    {63        scanf("%d",&N);64        for(int i=0;i<N;i++)scanf("%s%d%d",homework[i].name,&homework[i].deadline,&homework[i].cost);65        DP();66    }67     return 0;68 }
View Code

　　做这题做的很是沮丧，在DP（）中把j写成j+1了，看了很久愣是没看出来，慢慢调试了将近1小时后才发现。

 1 void DP() 2 { 3     int Final=(1<<N)-1,punish,previous; 4     dp[0].id=dp[0].now=dp[0].pre=dp[0].score=dp[0].time=0; 5     for(int i=1;i<=Final;i++)//状态从全0到全1 6     { 7         dp[i].score=10000000;//为了找出最小值所以先初始化成比较大的值 8         for(int j=0;j<N;j++)//题编号 9             if(i&(1<<j))//状态i中有题j,为什么这样写是因为保证在状态全一的时候10                 //枚举过每一种可能，即由状态previous转化成状态j11         {12              previous=(i-(1<<j));//从previous到i仅相差一个作业13              //若从状态previous再做一题总时间加起来超过了作业j的deadline，记录扣几分14              //否则为零15             if(dp[previous].time+homework[j].cost>homework[j].deadline)16                 punish=dp[previous].time+homework[j].cost-homework[j].deadline;17             else punish=0;18             //寻找状态为i时候的最小值19             if(dp[i].score>=dp[previous].score+punish)20             {21                 dp[i].score=dp[previous].score+punish;22                 dp[i].time =dp[previous].time+homework[j].cost;23                 dp[i].pre=previous;24                 dp[i].now=j;25             }26         }27     }28     printf("%d\n",dp[Final].score);29     //显示路径now代表的是状态i是由写了一道编号为now的题形成的，previous是i的前一状态30     int cal=Final,num=0;31     while(cal)32     {33         record[num++]=dp[cal].now;34         cal=dp[cal].pre;35     }36     for(int i=num-1;i>=0;i--)37     puts(homework[record[i]].name);38 39 }
View Code

 


联系
我们