首页 > 代码库 > HDU 1074 (状态压缩DP)
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<<15int 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\n",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 |
HDU 1074 (状态压缩DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。