hdoj 1074 Doing Homework 【状态压缩dp】

小灰灰 2022-08-12 12:59 159阅读 0赞

题目：[hdoj 1074 Doing Homework ][hdoj 1074 Doing Homework]

题意：给出一些任务15个，每个任务有截至时间和需要做的天数，超期一天扣一分，求让扣分最小的安排方案。

分析：用状态压缩枚举所有的状态，dp【st】表示在st状态下的最小扣分

转移方程：dp【st | (1<<i)】 = min( dp\[st | ( 1 << i ) \] , dp\[ st \] + 当前 i 超期的扣分 )

注意这个题目需要打印路径，所以还要一个数组保存状态的转移，递归输出结果即可。

代码：

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <iostream>
    using namespace std;
    const int N = 16;
    int dp[1<<N];
    struct Node
    {
        string s;
        int time,cost;
    };
    Node a[N];
    int pre[1<<N];
    int n;
    void Output(int status)
    {
        if(status==0)return;
        int t=0;
        for(int i=0;i<n;i++)
          if( (status&(1<<i))!=0 && (pre[status]&(1<<i))==0 )
          {
              t=i;
              break;
          }
        Output(pre[status]);
        cout<<a[t].s<<endl;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                cin>>a[i].s>>a[i].time>>a[i].cost;
            }
            memset(dp,0x3f3f3f3f,sizeof(dp));
            memset(pre,0,sizeof(pre));
            dp[0]=0;
            for(int st=0;st<(1<<n);st++)
            {
                //printf("**************************\n");
                int tmp=0;
                for(int i=0;i<n;i++)
                {
                    if(st&(1<<i))
                        tmp+=a[i].cost;
                }
                for(int i=0;i<n;i++)
                {
                    //printf("fff %d %d %d",st,(1<<i),st&(1<<i));
                    if((st&(1<<i))==0)
                    {
                        if(dp[st|(1<<i)]>dp[st]+max(0,tmp+a[i].cost-a[i].time)){
                            dp[st|(1<<i)]=dp[st]+max(0,tmp+a[i].cost-a[i].time);
                            pre[st|(1<<i)]=st;
                        }
                    }
                }
    
            }
            printf("%d\n",dp[(1<<n)-1]);
            Output((1<<n)-1);
        }
        return 0;
    }

[hdoj 1074 Doing Homework]: http://acm.hdu.edu.cn/showproblem.php?pid=1074