Hdu 1074 Doing Homework 状压dp

本是古典何须时尚 2022-08-21 14:48 8阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1074][http_acm.hdu.edu.cn_showproblem.php_pid_1074]

题目大意：给你n个科目，每个科目都有截止时间和需要完成的时间，每个科目超过截止时间一天都要在期末考试中扣一分，问所有的科目加起来最少扣多少分

解题思路：

结合代码说

int rec(int s,int v)
    {
        if(dp[s][v]>=0) return dp[s][v];
        if(s==(1<<n)-1) return dp[s][v]=0;
        int res=inf;
        for(int i=0; i<n; i++)
        {
            if(!(s>>i&1))
            {
                int x1=rec(s|1<<i,i),x2;
                if(!call[s][i]) x2=cal(s,i);
                else x2=call[s][i];
                if(res>x1+x2)  res=x1+x2;
    
            }
        }
        return dp[s][v]=res;
    }

s代表已完成的科目，v代表已完成的科目中最后一个完成的科目，  
dp\[ s \]\[ v \] **代表从当前的完成的科目到完成所有科目扣的最少分数**，当从当前状态向下一状态转移时，需要加上会扣掉的分数，假如当前状态为1 0 0 1，当向 1 1 0 1，需要加上做新科目需要扣的分数，至于扣多少分，根据里面的1计算一下就好了吧。

至于求完成顺序，我是直接模拟了一遍求答案的过程，但是因为dp\[s\]\[v\]都已经求出，所以求顺序的时间复杂度是n^2，n很小，也不碍事。  
比如刚开始是0 0 0 0，我枚举每一个值，判断转移到0001 或0010或0100或1000哪个最小，如果判断是转移到0010最小，那么再判断转移到1010 或 0110 或 0011哪个最小，一直如此判断。

因为刚学，代码写得有点low

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    
    int dp[1<<16][16],n;
    int ans[20];
    int call[1<<16][16];
    struct subject
    {
        int dead;
        int time;
    
    };
    subject sub[20];
    
    int cal(int x,int now)
    {
        int summ=0;
        for(int i=0; i<n; i++)
        {
            if(x>>i&1)  summ+=sub[i].time;
        }
        if(summ+sub[now].time>=sub[now].dead) return call[x][now]=summ+sub[now].time-sub[now].dead;
        return call[x][now]=0;
    }
    
    int rec(int s,int v)
    {
        if(dp[s][v]>=0) return dp[s][v];
        if(s==(1<<n)-1) return dp[s][v]=0;
        int res=inf;
        for(int i=0; i<n; i++)
        {
            int zhuangyi;
            if(!(s>>i&1))
            {
                int x1=rec(s|1<<i,i),x2;
                if(!call[s][i]) x2=cal(s,i);
                else x2=call[s][i];
                if(res>x1+x2)  res=x1+x2;
    
            }
        }
        return dp[s][v]=res;
    }
    
    
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            RI(n);
            char name [20][105];
            memset(dp,-1,sizeof(dp));
            mem(sub);
            mem(call);
            mem(ans);
            for(int i=0; i<n; i++)
            {
                scanf("%s %d %d",name[i],&sub[i].dead,&sub[i].time);
            }
            cout<<rec(0,0)<<endl;
            int tttt;
            int ss=0;
    
    
            for(int k=0; k<n; k++)
            {
                int minn=inf;
                for(int i=0; i < n; i++)
                {
                    if(!ans[i])
                    {
                        int x2;
                        if(call[ss][i]) x2=call[ss][i];
                        else x2=cal(ss,i);
                        if(minn>dp[ss|1<<i][i]+x2)
                        {
                            minn=dp[ss|1<<i][i]+x2;
                            tttt=i;
                        }
                    }
    
                }
                printf("%s\n",name[tttt]);
                ans[tttt]=1;
                ss=ss|1<<tttt;
            }
    
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1074]: http://acm.hdu.edu.cn/showproblem.php?pid=1074