HDU 1074 Doing Homework （状压dp）

题意：给你N（<=15）个作业，每个作业有最晚提交时间与需要做的时间，每次只能做一个作业，每个作业超出最晚提交时间一天扣一分

求出扣的最小分数，并输出做作业的顺序。如果有多个最小分数一样的话，则按照作业字典序输出（注意：输入也是按照字典序输入的）

题解：首先想到的是暴力dfs，但是会超时。接着我们看到n最大只有15，因此可以使用状压dp，但是状态不能用位置表示

但我们可以这样：0表示此作业没有做过，1表示已经用过了，接着遍历0->(1<<n)-1贪心（例如：3（011）可以找2（010）或者1（001）来计算）计算就好了，注意保存路径与字典序输出

注意我们要使用状压dp需要找到一个只有两种状态的事件

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=<<;//压缩成现在处理过（1）与没处理过（0）

const int Max2=;

char str[][Max2];

int deal[Max2],val[Max2],vis[Max];

int dp[][Max];//一位记录之前有几天 一位记录最小降低分数

void DP(int n)

{

    dp[][]=dp[][]=;//全没处理过

    vis[]=;

    int temp;

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

    {

        dp[][i]=Inf;

        temp=i;

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

        {

            int tmp=<<j;

            if((temp|tmp)==temp)//第j位有1

            {

                int minx=dp[][i-tmp]+max(,val[j]+dp[][i-tmp]-deal[j]);

                if(minx<=dp[][i])

                {

                    dp[][i]=minx;

                    dp[][i]=dp[][i-tmp]+val[j];

                    vis[i]=i-tmp;

                }

            }

        }

    }

    return;

}

int Lowday(int m)

{

    for(int i=;;m>>=,++i)

        if(!m)

            return i-;

}

void dfs(int now,int pre)

{

    if(!now)

    {

        printf("%s\n",str[Lowday(pre)]);

        return;

    }

    dfs(vis[now],now);

    printf("%s\n",str[Lowday(pre-now)]);

    return;

}

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

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

        {

            scanf("%s %d %d",str[i],&deal[i],&val[i]);

        }

        DP(n);

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

        dfs(vis[(<<n)-],(<<n)-);

    }

    return ;

}

HDU 1074 Doing Homework （状压dp）的相关教程结束。