HDU 1074 Doing Homework（状态压缩）

　　之前做过一个题,是在学贪心的时候做的,所以这个题就想当然的跑偏了,当看到N是<=16 的时候,状态压缩就理所当然了

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define INF 0x3f3f3f3f

struct Dp

{

    int reduce;

    int tim;

    int fa;

};

struct Course

{

    int d;

    int c;

    char name[];

};

Dp dp[<<];

Course cla[];

void print(int num)

{

    if(num <= )

        return;

    int temp,id = ;

    print(dp[num].fa);

    temp = dp[num].fa ^ num;

    while(! (temp & ) )

    {

        id++;

        temp >>= ;

    }

    printf("%s\n",cla[id].name);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

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

            scanf("%s%d%d",cla[i].name,&cla[i].d,&cla[i].c);

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

        {

            if(i == )

            dp[i].reduce = ;

            else dp[i].reduce = INF;

            dp[i].tim = ;

            dp[i].fa = -;

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

            {

                int temp = <<j;

                if(temp & i)

                {

                    dp[i].tim = dp[i^temp].tim + cla[j].c;

                    int reduces = dp[i].tim - cla[j].d;

                    if(reduces < ) reduces = ;

                    if(dp[i].reduce >= dp[i^temp].reduce + reduces)

                    {

                        dp[i].fa = i^temp;

                        dp[i].reduce = dp[i^temp].reduce + reduces;

                    }

                }

            }

        }

        printf("%d\n",dp[(<<n)-].reduce);

        print((<<n)-);

    }

    return ;

}