Doing Homework

D - Doing Homework

> 参考:ACM HDU 1074 Doing Homework(位运算,搜索,状态压缩DP)

> 思路:因为每个作业给定的顺序就是按照字典序的顺序,所以不用再多去比较。
>
> 该题的n不大,同时我们又想用DP来完成这道题,那么一个很好的办法来储存状态,就是状态压缩,利用二进制的特点来保存状态,0 为未完成,1 为已完成。那么在遍历的时候就只需要for(int i=0;i<=(1<<n)-1;++i)这样的方式来遍历即可,因为遍历到任何一个状态i的时候,它都已经是最优解了,因为所有能够到达i这种情况的方式都已经遍历过了。

代码:

// Created by CAD on 2019/10/23.
#include <bits/stdc++.h>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;
struct homework{
    string name;
    int deadline,spend;
}h[20];
struct state{
    int cost,reduce,pre;
    string name;
}dp[1<<15];
int vis[1<<15];
void print(int n)
{
    if(!n) return;
    print(dp[n].pre);
    cout<<dp[n].name<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;  cin>>t;
    while(t--)
    {
        int n;  cin>>n;
        for(int i=1;i<=n;++i)
            cin>>h[i].name>>h[i].deadline>>h[i].spend;
        int up=1<<n;
        dp[0].pre=-1,dp[0].reduce=0,dp[0].cost=0;
        mst(vis,0);
        vis[0]=1;
        for(int i=0;i<up-1;++i)
        {
            for(int j=0;j<n;++j)
            {
                int now=1<<j;
                if(!(now&i))
                {
                    int next=i|now;
                    int temp=dp[i].cost+h[j+1].spend;
                    dp[next].cost=temp;
                    int red=temp-h[j+1].deadline;
                    if(red<0) red=0;
                    red+=dp[i].reduce;
                    if(vis[next])
                    {
                        if(red<dp[next].reduce)
                            dp[next].reduce=red,dp[next].pre=i,dp[next].name=h[j+1].name;
                    }
                    else
                        vis[next]=true,dp[next].reduce=red,dp[next].pre=i,dp[next].name=h[j+1].name;
                }
            }
        }
        cout<<dp[up-1].reduce<<endl;
        print(up-1);
    }
    return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。