hdu 1074 状态压缩dp

逃离我推掉我的手 2022-08-20 08:27 181阅读 0赞

题意：

有n种不同的作业，每种作业有完成所需的时间以及截止上交的时间，每种作业超过截止时间上交会扣分，现在要你安排这n种作业的完成顺序使得总扣分最少。

分析：

由于n比较小最大只有15，那么我们就可以考虑使用状态压缩dp来完成，每种作业的一种完成方式是一个状态。

例如5，二进制位101，代表第一门和第三门完成了，第二门没有完成，那么我们可以枚举1~1<<n便可以得出所有的状态

对于到达状态i,从何种状态到达i呢？只需要枚举所有的作业，假如对于作业k,i中含有作业k已完成，那么i可以由和i状态相同的状态仅仅是k未完成的，状态j=i-(1<<k)来完成k到达,并且j一定比i小，如果状态从0枚举到2^n-1那么j一定是在i之前已经计算过的

详细看代码

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <stack>
    using namespace std;
    
    #define inf 100000000
    
    int const maxn = 16;
    
    struct node
    {
        int t,s;  //分别代表当前状态下的时间以及罚时
        int p,n;  //p和n用来记录完成作业的次序
    }dp[1<<maxn];
    
    int d[maxn],c[maxn];  //deal和const
    char name[maxn][105];
    
    int main()
    {
        int t,n,s;//s是当前的状态
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            for(int i = 0 ; i < n ; i++)
            {
                scanf("%s%d%d",name[i],&d[i],&c[i]);
            }
            s = 1<<n ;
            for(int i = 1 ; i < s ; i++)
            {
                //i为当前状态
                dp[i].s = inf ;
                for(int j = n-1 ; j >= 0 ; j--)
                {
                    int t = 1<<j ;  //j的状态
                    if(i&t)
                    {
                        int p = i - t ;                  //p为i出去j之前的状态
                        int so = dp[p].t + c[j] - d[j] ; //当前时间加上所需时间减去截止时间
                        if(so<0)so=0;                    //此时说明没有超出截止时间
                        if(dp[p].s+so < dp[i].s)
                        {
                            //如果前一个状态所花的时间和当前状态花的时间小于  已经确定的值，那么这样一种方法更省时
                            dp[i].s = dp[p].s+so;
                            dp[i].t = dp[p].t+c[j];
                            dp[i].n = j ;
                            dp[i].p = p ;
                        }
                    }
                }
            }
            s--;
            printf("%d\n",dp[s].s);
            stack <int> S;
            while(s)
            {
                S.push(dp[s].n);
                s = dp[s].p;
            }
            while(!S.empty())
            {
                printf("%s\n",name[S.top()]);
                S.pop();
            }
        }
        return 0;
    }