HDU1074 Doing Homework
题意：给了n个家庭作业，然后给了每个家庭作业的完成期限和花费的实践，如果完成时间超过了期限，那么就要扣除分数，然后让你找出一个最优方案使扣除的分数最少，当存在多种方案时，输出字典序最小的那种，因为题意已经说了家庭作业的名字是按照字典序从小到大输入的，所以处理起来就好多了。
分析：此题的关键是如何记录路径，具体看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath> using namespace std;
#define MAX 1<<15+1
int N;
struct Node{
char name[];
int deadline;
int cost;
}homework[];
struct START
{
int time;
int pre;
int score;
int now;
} dp[MAX];
int record[]; void DP()
{
int Final=(<<N)-,punish,previous;
dp[].id=dp[].now=dp[].pre=dp[].score=dp[].time=;
for(int i=;i<=Final;i++)
{
dp[i].score=;
for(int j=;j<N;j++)
if(i&(<<j))
{
previous=(i-(<<j));
if(dp[previous].time+homework[j].cost>homework[j].deadline)
punish=dp[previous].time+homework[j].cost-homework[j].deadline;
else punish=;
if(dp[i].score>=dp[previous].score+punish)
{
dp[i].score=dp[previous].score+punish;
dp[i].time =dp[previous].time+homework[j].cost;
dp[i].pre=previous;
dp[i].now=j;
}
}
}
printf("%d\n",dp[Final].score);
int cal=Final,num=;
while(cal)
{
record[num++]=dp[cal].now;
cal=dp[cal].pre;
}
for(int i=num-;i>=;i--)
puts(homework[record[i]].name); }
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(int i=;i<N;i++)scanf("%s%d%d",homework[i].name,&homework[i].deadline,&homework[i].cost);
DP();
}
return ;
}
做这题做的很是沮丧，在DP（）中把j写成j+1了，看了很久愣是没看出来，慢慢调试了将近1小时后才发现。
void DP()
{
int Final=(<<N)-,punish,previous;
dp[].id=dp[].now=dp[].pre=dp[].score=dp[].time=;
for(int i=;i<=Final;i++)//状态从全0到全1
{
dp[i].score=;//为了找出最小值所以先初始化成比较大的值
for(int j=;j<N;j++)//题编号
if(i&(<<j))//状态i中有题j,为什么这样写是因为保证在状态全一的时候
//枚举过每一种可能，即由状态previous转化成状态j
{
previous=(i-(<<j));//从previous到i仅相差一个作业
//若从状态previous再做一题总时间加起来超过了作业j的deadline，记录扣几分
//否则为零
if(dp[previous].time+homework[j].cost>homework[j].deadline)
punish=dp[previous].time+homework[j].cost-homework[j].deadline;
else punish=;
//寻找状态为i时候的最小值
if(dp[i].score>=dp[previous].score+punish)
{
dp[i].score=dp[previous].score+punish;
dp[i].time =dp[previous].time+homework[j].cost;
dp[i].pre=previous;
dp[i].now=j;
}
}
}
printf("%d\n",dp[Final].score);
//显示路径now代表的是状态i是由写了一道编号为now的题形成的，previous是i的前一状态
int cal=Final,num=;
while(cal)
{
record[num++]=dp[cal].now;
cal=dp[cal].pre;
}
for(int i=num-;i>=;i--)
puts(homework[record[i]].name); }