HDU 1074 (状态压缩DP)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1074

题目大意:有N个作业(N<=15),每个作业需耗时,有一个截止期限。超期多少天就要扣多少分。问最少被扣多少分,且按字典序输出做作业顺序。

解题思路

集合上的DP问题。也就是状态压缩DP。

用二进制位表示做作业的顺序。总bit=1<<15。

对于状态i,枚举当前的作业j,如果i&(1<<(j-1)),则表示当前状态含有作业j。

t^=(1<<(j-1)),还原出还没做j作业之前的状态,现在就有now和pre两个状态了。

计算pre状态下做j作业的扣分情况,+cost[j]-dead[j],没过期得到负数改为0。

dp转移时顺便记录下当前状态的日期,以及状态i做的是哪个作业j。

注意:因为题目要求是输出字典序小的方案,所以应该倒序循环当前作业j。

这里把思路倒一下,记录的是当前的作业,也就是后做的作业,如果正序循环,则表示先做字典序大的作业,后做字典序小的作业。

正好和题目要求相反了。

最后dp[bit-1]就是结果。

递归打印方案,从bit-1开始,每次^个(1<<j),递归终点则还原出一开始做的作业,输出即可。

#include "cstdio"
#include "string"
#include "iostream"
#include "cstring"
using namespace std;
#define maxn 1<<15
int dead[20],cost[20],dp[maxn],T[maxn],pre[maxn];
string sub[20];
void output(int x)
{
    if(!x) return;
    output(x^(1<<pre[x]));
    cout<<sub[pre[x]]<<endl;
}
int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int bit=1<<n;
        for(int i=0;i<n;i++)
            cin>>sub[i]>>dead[i]>>cost[i];
        for(int i=1;i<bit;i++)
        {
            dp[i]=1<<28;
            for(int j=n-1;j>=0;j--)
            {
                int tt=1<<j,reduce;
                if(!(i&tt)) continue;
                tt=i^tt;
                reduce=T[tt]+cost[j]-dead[j];
                reduce=reduce<0?0:reduce;
                if(dp[tt]+reduce<dp[i])
                {
                    dp[i]=dp[tt]+reduce;
                    T[i]=T[tt]+cost[j];
                    pre[i]=j;
                }
            }
        }
        printf("%d
",dp[bit-1]);
        output(bit-1);
        memset(pre,0,sizeof(pre));
    }
}
11693089 2014-09-21 01:25:25 Accepted 1074 15MS 676K 1166 B C++ Physcal
原文地址:https://www.cnblogs.com/neopenx/p/4048722.html