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 START 15 { 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 }
做这题做的很是沮丧,在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转化成状态j 11 { 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 }