hdu 1074(状态压缩dp+记录路径)

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

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

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

struct node{

    char str[];

    int dayline;

    int cost;

}a[];

struct st{

    int now,pre;//now代表当前状态，pre代表当前状态的前一个状态

    int time;//当前时间

    int score;//当前扣除的分数

    int id;//当前刚做完的作业

}dp[];

int n;

void solve()

{

    int i,j,max=<<n,qian,temp,num=;

    char res[][];

    dp[].now=;

    dp[].pre=;

    dp[].time=;

    dp[].score=;

    dp[].id=;

    for(i=;i<max;i++)

    {

        dp[i].score=;

        for(j=;j<=n-;j++)

        {

            if(i&(<<j))

            {

                qian=i-(<<j);//由qian->i

                if(dp[qian].time+a[j+].cost>a[j+].dayline)

                 temp=dp[qian].time+a[j+].cost-a[j+].dayline;

                else

                 temp=;

                //temp用来表示做了当前作业需要扣除的分数

                if(dp[i].score>=dp[qian].score+temp)//这里要取等号，自己想下为什么？如果去掉，会出现生命结果

                {

                    dp[i].score=dp[qian].score+temp;

                    dp[i].now=i;

                    dp[i].pre=qian;

                    dp[i].time=dp[qian].time+a[j+].cost;

                    dp[i].id=j+;

                }

            }

        }

    }

    printf("%d\n",dp[max-].score);

    int t=max-;

    while(dp[t].now!=)//先把结果倒过来

    {

        strcpy(res[num++],a[dp[t].id].str);

        t=dp[t].pre;

    }

    for(i=num-;i>=;i--)

     printf("%s\n",res[i]);

}

int main()

{

    int T,i;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        getchar();

        for(i=;i<=n;i++)

        {

            scanf("%s",a[i].str);

            scanf("%d",&a[i].dayline);

            scanf("%d",&a[i].cost);

            getchar();

        }

        solve();

    }

    return ;

}